47. Permutations II Medium

1/**
2 * [47] Permutations II
3 *
4 * Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
5 *  
6 * Example 1:
7 *
8 * Input: nums = [1,1,2]
9 * Output:
10 * [[1,1,2],
11 *  [1,2,1],
12 *  [2,1,1]]
13 *
14 * Example 2:
15 *
16 * Input: nums = [1,2,3]
17 * Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
18 *
19 *  
20 * Constraints:
21 *
22 * 1 <= nums.length <= 8
23 * -10 <= nums[i] <= 10
24 *
25 */
26pub struct Solution {}
27
28// problem: https://leetcode.com/problems/permutations-ii/
29// discuss: https://leetcode.com/problems/permutations-ii/discuss/?currentPage=1&orderBy=most_votes&query=
30
31// submission codes start here
32
33impl Solution {
34    pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
35        let mut sorted_nums = nums.clone();
36        sorted_nums.sort();
37        let mut used = vec![false; sorted_nums.len()];
38        let mut result = Vec::new();
39        Self::backtrack(&sorted_nums, &mut result, &mut Vec::new(), &mut used);
40        result
41    }
42
43    fn backtrack(
44        nums: &Vec<i32>,
45        result: &mut Vec<Vec<i32>>,
46        current: &mut Vec<i32>,
47        used: &mut Vec<bool>,
48    ) {
49        if current.len() == nums.len() {
50            result.push(current.clone());
51            return;
52        }
53
54        for i in 0..nums.len() {
55            if used[i] || (i > 0 && used[i - 1] && nums[i] == nums[i - 1]) {
56                continue;
57            }
58            used[i] = true;
59            current.push(nums[i]);
60            Self::backtrack(nums, result, current, used);
61            current.pop();
62            used[i] = false;
63        }
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_47() {
75        println!("{:#?}", Solution::permute_unique(vec![1,2,1]));
76    }
77}
78