78/90-子集

LeetCode 78. Subsets

LeetCode-78

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

method: 回溯

组合问题是收集树的叶子节点，子集问题是收集树的所有节点
不能包含重复元素，所以从i+1开始

vector<vector<int>> ret;
vector<int> path;
void traversal(vector<int> nums, int index) {
    ret.push_back(path);    // 收集所有节点
    for (int i = index; i < nums.size(); ++i) {
        path.push_back(nums[i]);
        traversal(nums, i + 1);
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    traversal(nums, 0);
    return ret;
}

---

LeetCode 90. Subsets II

LeetCode-90

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

method: 回溯

数组里有重复元素，但是要求子集不能重复
和组合总和II一样的去重方式

1. 排序
2. 如果当前元素和上一个元素相同就跳过

vector<vector<int>> ret;
vector<int> path;
void traversal(vector<int>& nums, int index) {
    ret.push_back(path);
    for (int i = index; i < nums.size(); ++i) {
        if (i > index && nums[i] == nums[i - 1]) continue;  // 2
        path.push_back(nums[i]);
        traversal(nums, i + 1);
        path.pop_back();
    }
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // 1
    traversal(nums, 0);
    return ret;
}