46. Permutations Medium

1/**
2 * [46] Permutations
3 *
4 * Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
5 *  
6 * Example 1:
7 * Input: nums = [1,2,3]
8 * Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
9 * Example 2:
10 * Input: nums = [0,1]
11 * Output: [[0,1],[1,0]]
12 * Example 3:
13 * Input: nums = [1]
14 * Output: [[1]]
15 *  
16 * Constraints:
17 *
18 * 1 <= nums.length <= 6
19 * -10 <= nums[i] <= 10
20 * All the integers of nums are unique.
21 *
22 */
23pub struct Solution {}
24
25// problem: https://leetcode.com/problems/permutations/
26// discuss: https://leetcode.com/problems/permutations/discuss/?currentPage=1&orderBy=most_votes&query=
27
28// submission codes start here
29use std::collections::HashSet;
30
31impl Solution {
32    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
33        let mut result = Vec::new();
34        Self::backtrack(&nums, &mut HashSet::new(), &mut vec![], &mut result);
35        result
36    }
37
38    fn backtrack(
39        nums: &Vec<i32>,
40        set: &mut HashSet<i32>,
41        current: &mut Vec<i32>,
42        result: &mut Vec<Vec<i32>>,
43    ) {
44        if nums.len() == current.len() {
45            result.push(current.clone());
46        }
47
48        for n in nums {
49            if !set.contains(n) {
50                set.insert(*n);
51                current.push(*n);
52                Self::backtrack(nums, set, current, result);
53                set.remove(n);
54                current.pop();
55            }
56        }
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_46() {
68        println!("Got {:#?}", Solution::permute(vec![1,2,3]))
69    }
70}
71