1
2

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

1
2

输入：nums = [0]
输出：[[],[0]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 回溯法(dfs)
    /// 1. 首先对所有的整数排序;
    /// 2. 遍历访问时, 跳过和前一元素相等的重复元素;
    pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
        fn dfs(nums: &Vec<i32>, from: usize, tmp: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
            // 递归终止条件
            if from >= nums.len() {
                return;
            }
            for i in from..nums.len() {
                // 跳过重复出现过的数字
                if i > from && nums[i] == nums[i - 1] {
                    continue;
                }
                tmp.push(nums[i]);
                res.push(tmp.clone());
                dfs(nums, i + 1, tmp, res);
                tmp.pop();
            }
        }

        let mut tmp = Vec::new();
        let mut res = Vec::new();

        res.push(tmp.clone());
        let mut nums = nums;
        nums.sort(); // 将原序列排序
        dfs(&nums, 0, &mut tmp, &mut res);

        res
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    vector<vector<int>> result;
public:
    /*
    * ## 解题思路
    * * 回溯法
    * 去重主要有2点：
    * 1. 先对nums进行排序；
    * 2. 在深度遍历前，跳过重复元素层级的递归调用；
    */
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> tmp;
        sort(nums.begin(), nums.end());
        result.push_back(tmp);
        dfs(nums, tmp, 0);
        return result;
    }

    void dfs(vector<int>&nums, vector<int>&tmp, int s) {
        if (s>=nums.size()) {
            return;
        }

        for(int i=s; i<nums.size(); i++) {
            // 跳过本级重复的，不往下深度遍历
            if (i>s && nums[i] == nums[i-1]) {
                continue;
            }
            tmp.push_back(nums[i]);
            result.push_back(tmp);
            dfs(nums, tmp, i+1);
            tmp.pop_back();
        }
    }
};