西安网站维护兼职,关键词快速排名不限行业,网站管理与维护方案,织梦cms手机网站源码1. 题目
给定一个数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明#xff1a; 所有数字#xff08;包括目标数#xff09;都是正整数。 解集不能包含重…1. 题目
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明 所有数字包括目标数都是正整数。 解集不能包含重复的组合。
示例 1:
输入: candidates [10,1,2,7,6,1,5], target 8,
所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]示例 2:
输入: candidates [2,5,2,1,2], target 5,
所求解集为:
[[1,2,2],[5]
]来源力扣LeetCode 链接https://leetcode-cn.com/problems/combination-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 类似题目 LeetCode 216. 组合总和 III排列组合 回溯 LeetCode 39. 组合总和排列组合 回溯
2. 回溯求解
class Solution {
public:vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());vectorvectorint ans;vectorint subset;bt(0,0,target,subset,ans,candidates);return ans;}void bt(int i, int sum, int target, vectorint subset, vectorvectorint ans, vectorint candidates) {if(i candidates.size() || sum target)return;if(i candidates.size() sum target){ans.push_back(subset);return;}for(int j i; j candidates.size(); j){if(j i candidates[j-1] candidates[j])continue;subset.push_back(candidates[j]);bt(j1, sumcandidates[j], target, subset, ans, candidates);subset.pop_back();}}
};8 ms 7.1 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
