首页 > 代码库 > [LeetCode系列]组合和枚举问题
[LeetCode系列]组合和枚举问题
给定一列数(未排序)和一个目标值, 找出所有可能的组合和等于目标值的组合, 数组中的数可以重复使用.
算法思路: 使用递归.
- 对数组排序, 从小到大;
- 令i = 起始下标(初始为0), 对于每一个数,
- 如果它等于目标值, 则在缓存结果中加入此数并将缓存结果加入输出队列, 随后在缓存结果中删除此数;
- 如果它小于目标值, 则在缓存结果中加入此数并递归调用此算法, 目标值更新为差值, 起始下标为i;
- 如果它大于目标值, 算法返回.
对于2.2的理解: 如果这个数小于目标值, 由于算法是循环递归, 那么起始的下标必定不能小于i(否则出现重复情况).
代码:
1 class Solution { 2 public: 3 vector<vector<int> > combinationSum(vector<int> &candidates, int target) { 4 vector<int> A(candidates); 5 vector<int> oneRes; 6 vector<vector<int> > result; 7 sort(A.begin(), A.end()); 8 helper(A, target, oneRes, result, 0); 9 return result;10 }11 12 void helper(vector<int> A, int target, vector<int> &oneRes, vector<vector<int> > &result, int start) {13 for (int i = start; i < A.size(); i++) {14 if (A[i] == target) {15 oneRes.push_back(A[i]);16 result.push_back(oneRes);17 oneRes.pop_back();18 }19 else if (A[i] < target) {20 oneRes.push_back(A[i]);21 helper(A, target-A[i], oneRes, result, i);22 oneRes.pop_back();23 }24 else return;25 }26 }27 };
[LeetCode系列]组合和枚举问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。