47. Permutations II

Description

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

Solutions

Solution 1: Sorting + Backtracking

We can first sort the array, which allows us to place duplicate numbers together, making it easier for us to remove duplicates.

Next, we design a function $dfs(i)$, indicating that we need to fill in the number at the $i$th position. The specific implementation of the function is as follows:

If $i = n$, it means we have finished filling in, add the current permutation to the answer array, and then return.
Otherwise, we enumerate the number $nums[j]$ at the $i$th position, where the range of $j$ is $[0, n - 1]$. We need to ensure that $nums[j]$ has not been used and is different from the number enumerated before, so as to ensure that the current permutation is not repeated. If the conditions are met, we can fill in $nums[j]$, and continue to recursively fill in the next position, that is, call $dfs(i + 1)$. After the recursive call ends, we need to mark $nums[j]$ as unused for later enumeration.

In the main function, we first sort the array, then call $dfs(0)$, that is, start filling from the 0th position, and finally return the answer array.

The time complexity is $O(n \times n!)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array. We need to enumerate $n!$ times, and each enumeration takes $O(n)$ time to judge whether it is repeated. In addition, we need a marker array to mark whether each position has been used, so the space complexity is $O(n)$.

In python solution, why conditional statement `if i > 0 and perm[i - 1] == num:`

The conditional statement if i > 0 and perm[i - 1] == num: in the provided code is crucial for eliminating duplicate permutations when generating all unique permutations of a list of numbers, some of which may be duplicates. This line is the key to handling duplicates effectively, ensuring that each unique permutation is only added once to the result.

Explanation with Example

Suppose nums = [1, 1, 2]. After sorting, nums remains [1, 1, 2].

Initially, res = [[]], meaning we start with an empty permutation.
When the first 1 is processed, it can be inserted into the empty list in one position, resulting in [[1]].
As we process the second 1, the condition if i > 0 and perm[i - 1] == num: becomes important. Without this check, inserting the second 1 into [1] would produce two identical permutations: [1, 1] and [1, 1], because the second 1 can be placed at two different positions (at the start and after the first 1), but both positions result in the same list due to the numbers being identical.

Why the Condition Works

i > 0: This ensures the check is only made if there’s a previous element in the current permutation to compare with. It prevents an index out of range error and ensures we’re only checking for duplicates when there’s something to compare to.
perm[i - 1] == num: This checks if the current number (num) is the same as the number immediately before the current insertion point (perm[i - 1]). If true, it means inserting num at this point would result in a duplicate permutation that’s already been or will be generated by inserting num at an earlier point.

By breaking the loop when this condition is met, we skip over any insertion points that would lead to duplicate permutations, as any further insertions of the same number would only replicate sequences already considered.

Result

The loop break effectively prunes the search space, preventing the generation of duplicate permutations and ensuring the uniqueness of each permutation in res.

Detailed Walkthrough

For nums = [1, 1, 2], and currently processing the second 1, we attempt to insert it into existing permutations of res.
The first insertion position is before the first 1 in [1], yielding [1, 1].
The second possible position is after the first 1 in [1], but if i > 0 and perm[i - 1] == num: triggers because perm[i - 1] is also 1. The condition tells us inserting 1 here would duplicate the permutation just created, so we break and avoid further insertions.

This strategy ensures the algorithm generates all unique permutations of a set, including when duplicates are present, by methodically avoiding duplicate sequence generation through strategic pruning.

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int[] nums;
    private boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        vis = new boolean[nums.length];
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            t.add(nums[j]);
            vis[j] = true;
            dfs(i + 1);
            vis[j] = false;
            t.remove(t.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> t(n);
        vector<bool> vis(n);
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans.emplace_back(t);
                return;
            }
            for (int j = 0; j < n; ++j) {
                if (vis[j] || (j && nums[j] == nums[j - 1] && !vis[j - 1])) {
                    continue;
                }
                t[i] = nums[j];
                vis[j] = true;
                dfs(i + 1);
                vis[j] = false;
            }
        };
        dfs(0);
        return ans;
    }
};

from typing import List
class Solution: # iterative, if new_perm not in new_res
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = [[]]

        if nums is None or len(nums) == 0:
            return res

        for num in nums:
            new_res = []
            for perm in res:
                for i in range(len(perm) + 1):
                    new_perm = perm[:i] + [num] + perm[i:]
                    if new_perm not in new_res:  # Check for uniqueness
                        new_res.append(new_perm)

            res = new_res

        return res

##############

class Solution: # iterative
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # sort the input to handle duplicates
        res = [[]]
        for num in nums:
            new_res = []
            for perm in res:
                for i in range(len(perm) + 1):
                    if i > 0 and perm[i - 1] == num:
                    # added for lc-47, as explained above "Why the Condition Works"
                        break # skip duplicate
                    new_perm = perm[:i] + [num] + perm[i:]
                    # or perm.insert(index, num), like in lc-46
                    new_res.append(new_perm)
            res = new_res
        return res

############


class Solution: # dfs
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == n:
                ans.append(t[:])
                return
            for j in range(n):
                if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
                    continue
                t[i] = nums[j]
                vis[j] = True
                dfs(i + 1)
                vis[j] = False

        n = len(nums)
        nums.sort()
        ans = []
        t = [0] * n
        vis = [False] * n
        dfs(0)
        return ans

func permuteUnique(nums []int) (ans [][]int) {
	sort.Ints(nums)
	n := len(nums)
	t := make([]int, n)
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, slices.Clone(t))
			return
		}
		for j := 0; j < n; j++ {
			if vis[j] || (j > 0 && nums[j] == nums[j-1] && !vis[j-1]) {
				continue
			}
			vis[j] = true
			t[i] = nums[j]
			dfs(i + 1)
			vis[j] = false
		}
	}
	dfs(0)
	return
}

function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans: number[][] = [];
    const t: number[] = new Array(n);
    const vis: boolean[] = new Array(n);
    const dfs = (i: number) => {
        if (i === n) {
            ans.push(t.slice());
            return;
        }
        for (let j = 0; j < n; ++j) {
            if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            t[i] = nums[j];
            vis[j] = true;
            dfs(i + 1);
            vis[j] = false;
        }
    };
    dfs(0);
    return ans;
}

public class Solution {
    private List<IList<int>> ans = new List<IList<int>>();
    private List<int> t = new List<int>();
    private int[] nums;
    private bool[] vis;

    public IList<IList<int>> PermuteUnique(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        vis = new bool[n];
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.Length) {
            ans.Add(new List<int>(t));
            return;
        }
        for (int j = 0; j < nums.Length; ++j) {
            if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            vis[j] = true;
            t.Add(nums[j]);
            dfs(i + 1);
            t.RemoveAt(t.Count - 1);
            vis[j] = false;
        }
    }
}

use std::collections::HashSet;
impl Solution {
    fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        let n = nums.len();
        if i == n {
            res.push(nums.clone());
            return;
        }
        let mut set = HashSet::new();
        for j in i..n {
            if set.contains(&nums[j]) {
                continue;
            }
            set.insert(nums[j]);
            nums.swap(i, j);
            Self::dfs(i + 1, nums, res);
            nums.swap(i, j);
        }
    }

    pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        Self::dfs(0, &mut nums, &mut res);
        res
    }
}

47 - Permutations II

47. Permutations II

Description

Solutions

In python solution, why conditional statement `if i > 0 and perm[i - 1] == num:`

Explanation with Example

Why the Condition Works

Result

Detailed Walkthrough

All Problems

All Solutions

Welcome to Subscribe On Youtube

47. Permutations II

Description

Solutions

In python solution, why conditional statement if i > 0 and perm[i - 1] == num:

Explanation with Example

Why the Condition Works

Result

Detailed Walkthrough

All Problems

All Solutions

In python solution, why conditional statement `if i > 0 and perm[i - 1] == num:`