04 组合问题
# LeetCode刷题笔记 回溯算法
# 77 组合 (opens new window)
给定两个整数 n
和 k
,返回范围 [1, n]
中所有可能的 k
个数的组合。
你可以按 任何顺序 返回答案。
输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
解析:
class Solution {
public:
void bt(int n, int k, int start, vector<int>& track, vector<vector<int>>& ans){
if(track.size()==k){
ans.push_back(track);
return;
}
for(int i=start;i<=n;++i){
track.push_back(i);
bt(n,k,i+1,track,ans);
track.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
vector<int> track;
vector<vector<int>> ans;
bt(n,k,1,track,ans);
return ans;
}
};
# 39 组合总和 (opens new window)
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
输入:candidates = [2,3,6,7], target = 7 输出:[[2,2,3],[7]] 解释:2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选, 7 = 7 。仅有这两种组合。
解析:
class Solution {
public:
void bt(vector<int> candidates, int target, int start, vector<int>& track, vector<vector<int>>& ans){
// 超出总和减枝
if(target < 0){
return;
}
if(target==0){
ans.push_back(track);
return;
}
for(int i=start;i<candidates.size();++i){
track.push_back(candidates[i]);
bt(candidates,target-candidates[i],i,track,ans); // start 仍从 i 开始重复使用元素
track.pop_back();
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> track;
vector<vector<int>> ans;
bt(candidates,target,0,track,ans);
return ans;
}
};
# 40 组合总和 II (opens new window)
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 ,解集不能包含重复的组合
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
解析:
class Solution {
public:
void bt(vector<int>& candidates, int target, int start, vector<int>& track, vector<vector<int>>& ans, vector<bool>& visited){
if(target < 0){
return;
}
if(target==0){
ans.push_back(track);
return;
}
for(int i=start;i<candidates.size();++i){
if(i>start && candidates[i] == candidates[i-1] && !visited[i-1]){
continue;
}
track.push_back(candidates[i]);
visited[i] = true;
bt(candidates,target-candidates[i],i+1,track,ans,visited); // 元素不可重复利用,使用下一个即i+1
visited[i] = false;
track.pop_back();
}
return;
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> track;
vector<vector<int>> ans;
vector<bool> visited(candidates.size(),false);
sort(candidates.begin(),candidates.end());
bt(candidates,target,0,track,ans,visited);
return ans;
}
};
上次更新: 2023/11/19, 12:55:48