46. Permutations

求不同元素的全排列

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路：dfs

1. 设置一个答案数组
2. 设置一个临时路径数组
3. 用loop和contains判断元素是否在数组中，如果没有就添加
4. 添加后用现有的path进行递归，寻找path在nums中没有出现的数字nums[i]，图中列表中最后一个元素代表所找到最后一个元素
5. 递归完成后pop最后一个元素

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(nums, path, res);
    return res;
}

public void dfs(int[] nums, List<Integer> path, List<List<Integer>> res) {
    // return the base case
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }

    // loop the path
    for (int i = 0; i < nums.length; i++) {
        if (path.contains(nums[i])) continue;
        path.add(nums[i]);
        dfs(nums, path, res);
        path.remove(path.size() - 1);
    }
}

update: 04-07-2019

使用全局boolean数组记录用过的数字

class Solution {
    static boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        // boundary check
        if (nums == null || nums.length == 0) return new ArrayList<>();

        used = new boolean[nums.length];

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(nums, res, path);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                // System.out.println("level: " + path.size() + " use " + nums[i] + " result " + path + " used" + Arrays.toString(used));
                dfs(nums, res, path);
                path.remove(path.size() - 1);
                used[i] = false;
                // System.out.println("level: " + path.size() + " set " + nums[i] + " unused");
            }
        }
    }
}

print大法debug

level: 0 use 1 result [1] used[true, false, false]
level: 1 use 2 result [1, 2] used[true, true, false]
level: 2 use 3 result [1, 2, 3] used[true, true, true]
level: 2 set 3 unused
level: 1 set 2 unused  // 此时 --> used[true, false, false]
level: 1 use 3 result [1, 3] used[true, false, true]
level: 2 use 2 result [1, 3, 2] used[true, true, true]
level: 2 set 2 unused
level: 1 set 3 unused
level: 0 set 1 unused
level: 0 use 2 result [2] used[false, true, false]
level: 1 use 1 result [2, 1] used[true, true, false]
level: 2 use 3 result [2, 1, 3] used[true, true, true]
level: 2 set 3 unused
level: 1 set 1 unused
level: 1 use 3 result [2, 3] used[false, true, true]
level: 2 use 1 result [2, 3, 1] used[true, true, true]
level: 2 set 1 unused
level: 1 set 3 unused
level: 0 set 2 unused
level: 0 use 3 result [3] used[false, false, true]
level: 1 use 1 result [3, 1] used[true, false, true]
level: 2 use 2 result [3, 1, 2] used[true, true, true]
level: 2 set 2 unused
level: 1 set 1 unused
level: 1 use 2 result [3, 2] used[false, true, true]
level: 2 use 1 result [3, 2, 1] used[true, true, true]
level: 2 set 1 unused
level: 1 set 2 unused
level: 0 set 3 unused