题目描述

题目链接：46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例1：

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2：

1 2	输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例3：

1 2	输入：nums = [1] 输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

我的题解

方法一：回溯法

思路

非常经典的递归题目，对于nums = [1,2,3]，我们很容易想到：

先选取第一个数1，再选取第二个数2，最后选取3，得到一个答案1,2,3，加入答案数组；然后回溯上一个操作，不选3，不选2，选3，再选2，我们得到了另一个答案[1,3,2]。

因此我们需要一个标记数组标记当前数字是否已被选择，当得到一个答案之后回溯上一个选择即可。

代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        List<Integer> r = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, flag, result, r);
        return result;
    }

    private void dfs(int[] nums, boolean[] flag, List<List<Integer>> result, List<Integer> r) {
        if (r.size() == nums.length) {
            result.add(new ArrayList<>(r));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flag[i]) {
                r.add(nums[i]);
                flag[i] = true;
                dfs(nums, flag, result, r);
                r.remove(r.size() - 1);
                flag[i] = false;
            }
        }
    }
}