LeetCode 78.子集
问题描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
问题分析
- 此题本质是求组合问题，由于解集中不包含重复的子集，所以不用index数组来保存解集中数字的下标（为了保证回溯的时候不重复访问）。
- 为了防止由于元素位置调换而出现重复子集，所以每次调用backtrack时应该传入遍历的起始位置参数，避免出现位置不同而元素相同的子集。
代码实现（C++）
class Solution {
public:
vector<vector<int>> ans;
void backtrack(vector<int>nums, int start, vector<int>track){
int n = nums.size();
if (find(ans.begin(), ans.end(), track) == ans.end()){
ans.push_back(track);
}
for (int i=start; i<n; i++){
if(find(track.begin(), track.end(), nums[i]) == track.end()){
track.push_back(nums[i]);
backtrack(nums, i+1, track);
track.pop_back();
}
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> track;
backtrack(nums, 0, track);
return ans;
}
};
