LeetCode 46. Permutations

Question

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Source: https://leetcode.com/problems/permutations/

Solution

A conveninent condition provided by this question is that all elements are distinct. Thus, we do not need to consider duplicates of result.

The following solution is based on swap() so that it does not require additional space to store intermediate result of permutations. The idea is similar to selection sort. We treat elements before position as a determined permutation prefix, treat element after position as available elements in future searches. Another point is backtracking. Because all operations are on the same array nums, we need to recover changes of subtrees before diving into another path.

A common trick for DFS problems is to draw a DFS tree.

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

// the depth of dfs equals to the length of the array
// elements before position are regarded as fixed
private void dfs(int[] nums, int position, List<List<Integer>> result) {
    if (position == nums.length - 1) {
        List<Integer> permutation = new ArrayList<>();
        for (int n : nums) {
            permutation.add(n);
        }
        result.add(permutation);
    }

    // CANNOT guarantee that result will be de-deduplicated
    for (int i = position; i < nums.length; i++) {
        // backtrace
        swap(nums, position, i);
        dfs(nums, position + 1, result);
        swap(nums, position, i);
    }
}

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