YSMull
<-- algorithm



原题链接

类似带重复元素的全排列,记得对数组先进行排序,从而把所有相同的元素放到一起。

impl Solution {
    pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        let mut vis: Vec<_> = nums.iter().map(|i| false).collect();
        nums.sort();
        Solution::subsets_0(&nums, 0, &mut vec![], &mut vis, &mut res);
        return res;
    }

    fn subsets_0(nums: &Vec<i32>, i: usize, cur: &mut Vec<i32>, vis: &mut Vec<bool>, res: &mut Vec<Vec<i32>>) {
        if i == nums.len() {
            res.push(cur.clone());
            return;
        }
        // 选这个数
        if i == 0 || nums[i] != nums[i - 1] || (nums[i] == nums[i - 1] && vis[i - 1]) {
            cur.push(nums[i]);
            vis[i] = true;
            Solution::subsets_0(nums, i + 1, cur, vis, res);
            vis[i] = false;
            cur.pop();
        }
        // 不选这个数
        Solution::subsets_0(nums, i + 1, cur, vis, res);
    }
}