Permutations

Order does matter. You can still use the previous candidates. O(n!)

Question (LC.46)

Analysis

what's different from subsets?

you can use the previous candidates that are not used at this level

          []
         [1]
        /   \
    [1,2]   [1, 3]
    /          \!!! we can still add 2 here (not in subsets)
[1,2,3]     [1, 3, 2]


Think of it we are doing a bfs at each level [1, ?]
No need for a startIndex

Code

Main function

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    boolean[] used = new boolean[nums.length];
    Arrays.sort(nums);
    permDFS(results, nums, used, new ArrayList<Integer>());
    return results;
}

DFS Search

private void permDFS(List<List<Integer>> results, int[] nums, 
                boolean[] used, List<Integer> permutation) {
    // stop condition
    if (permutation.size() == nums.length) {
        results.add(new ArrayList<>(permutation));
        return;
    }
    // dfs
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) { // skip candidate if already used
            continue;
        }
        permutation.add(nums[i]);
        used[i] = true;
        permDFS(results, nums, used, permutation);
        permutation.remove(permutation.size() - 1);
        used[i] = false;
    }
}

To Do

general dfs approach

insertion iterative approach

swapping approach??

Follow Up Question (LC.47)

What if the input has duplicates? Then we skip duplicates!

// skip duplicates
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
    continue;
}

For example, we have [1, 2, 2]. We want $[1, 2_1, 2_2]$ instead of $[1, 2_2, 2_1]$.