> LeetCode46. 全排列 - Yuyy
Yuyy
Yuyy
LeetCode46. 全排列

一、介绍

这是基础的回溯题了。

二、题目

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
Related Topics
  • 回溯算法
  • \n

  • 👍 1046
  • 👎 0
  • 三、代码

    class Solution {
            private List<List<Integer>> ans;
    
            private int[][] nums;
    
            private List<Integer> tmp;
    
            public List<List<Integer>> permute(int[] nums) {
                tmp = new ArrayList<>();
                ans = new ArrayList<>();
                this.nums = new int[nums.length][];
                for (int i = 0; i < nums.length; i++) {
                    this.nums[i] = new int[2];
                    this.nums[i][0] = nums[i];
                    this.nums[i][1] = 0;
                }
                dfs();
                return this.ans;
            }
    
            public void dfs() {
                if (tmp.size() == nums.length) {
                    List<Integer> list = new ArrayList<>();
                    list.addAll(tmp);
                    ans.add(list);
                    return;
                }
    
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i][1] == 0) {
                        nums[i][1] = 1;
                        tmp.add(nums[i][0]);
                        dfs();
                        tmp.remove(tmp.size() - 1);
                        nums[i][1] = 0;
                    }
                }
            }
        }
    

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode46. 全排列
    一、介绍 这是基础的回溯题了。 二、题目 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], […
    扫描二维码继续阅读
    2021-01-27
    友情链接
    标签
    归档
    近期文章