面试金典-08.04 幂集

📝题目

编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

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

输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

📝思路

依旧是回溯法，看到幂集就应该联想到离散数学里面是如何得到一个集合的所有子集的：

即对集合中每个元素，都有两种选择：放入与不放入。遍历完所有元素后即可得到所有子集。

📝题解

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    backtrack(res, nums, {}, 0);
    return res;
}

void backtrack(vector<vector<int>>& res, vector<int>& nums, vector<int> trackList, int depth) {
    if (depth == nums.size()) {
        res.push_back(trackList);
        return;
    }
    // 放nums[depth]
    trackList.push_back(nums[depth]);
    backtrack(res, nums, trackList, depth+1);
    trackList.pop_back();
    //不放nums[depth]
    backtrack(res, nums, trackList, depth+1);        
}