39
40
78. Subsets https://leetcode.com/problems/subsets/description/
void subsets(vector<int>& nums, int pos, vector<int>& current, vector<vector<int>>& result){
if(pos == nums.size()){
result.push_back(current);
return;
}else{
subsets(nums,pos+,current,result);
current.push_back(nums[pos]);
subsets(nums,pos+,current,result);
current.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
subsets(nums, , current, result);
return result;
}
使用迭代的方法来做呢？
90. Subsets II https://leetcode.com/problems/subsets-ii/description/
void getsubsetsWithDup(vector<int>& nums, int pos, vector<int>& temp, vector<vector<int>>& result) {
if (pos == nums.size()) {
result.emplace_back(temp);
return;
}
//nextpos指向下一个不为nums[pos]的位置或为nums.size()
int nextpos = pos + ;
while (nextpos != nums.size() && nums[nextpos] == nums[pos])
nextpos++;
getsubsetsWithDup(nums, nextpos, temp, result);
for (int i = pos; i < nextpos; i++) {
temp.emplace_back(nums[i]);
getsubsetsWithDup(nums, nextpos, temp, result);
}
temp.erase(temp.end() - (nextpos - pos), temp.end());
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
vector<int> temp;
getsubsetsWithDup(nums, , temp, result);
return result;
}
1、重复的地方在与多个重复元素在一起的时候会出现前一个在、后一个不再和前一个不在、后一个在的这种重复情况，想要去除就在遇到这种情况的时候直接跳过，用不重复的情况代替，不重复的情况是确定个数的重复元素
216. Combination Sum III https://leetcode.com/problems/combination-sum-iii/description/
class Solution {
public:
/*
pos：遍历到1到9中的哪个位置
current：当前的数组
*/
void combinationSum3(vector<vector<int>>& result, int k ,int n, int pos,vector<int>& current){
if(n == && k== ){
result.push_back(current);
return;
}else if(n <= || k <= || pos > )
return;
else{
for(int i=pos;i<=;i++){
if(n-i<) return;
current.push_back(i);
combinationSum3(result,k-,n-i,i+,current);
current.pop_back();
}
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> current;
combinationSum3(result, k, n, , current);
return result;
}
};