C++实现LeetCode(39.组合之和)
[LeetCode] 39. Combination Sum 组合之和
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
像这种结果要求返回所有符合要求解的题十有八九都是要利用到递归，而且解题的思路都大同小异，相类似的题目有 Path Sum II，Subsets II，Permutations，Permutations II，Combinations 等等，如果仔细研究这些题目发现都是一个套路，都是需要另写一个递归函数，这里我们新加入三个变量，start 记录当前的递归到的下标，out 为一个解，res 保存所有已经得到的解，每次调用新的递归函数时，此时的 target 要减去当前数组的的数，具体看代码如下：
解法一：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> out;
combinationSumDFS(candidates, target, 0, out, res);
return res;
}
void combinationSumDFS(vector<int>& candidates, int target, int start, vector<int>& out, vector<vector<int>>& res) {
if (target < 0) return;
if (target == 0) {res.push_back(out); return;}
for (int i = start; i < candidates.size(); ++i) {
out.push_back(candidates[i]);
combinationSumDFS(candidates, target - candidates[i], i, out, res);
out.pop_back();
}
}
};
我们也可以不使用额外的函数，就在一个函数中完成递归，还是要先给数组排序，然后遍历，如果当前数字大于 target，说明肯定无法组成 target，由于排过序，之后的也无法组成 target，直接 break 掉。如果当前数字正好等于 target，则当前单个数字就是一个解，组成一个数组然后放到结果 res 中。然后将当前位置之后的数组取出来，调用递归函数，注意此时的 target 要减去当前的数字，然后遍历递归结果返回的二维数组，将当前数字加到每一个数组最前面，然后再将每个数组加入结果 res 即可，参见代码如下：
解法二：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
for (int i = 0; i < candidates.size(); ++i) {
if (candidates[i] > target) break;
if (candidates[i] == target) {res.push_back({candidates[i]}); break;}
vector<int> vec = vector<int>(candidates.begin() + i, candidates.end());
vector<vector<int>> tmp = combinationSum(vec, target - candidates[i]);
for (auto a : tmp) {
a.insert(a.begin(), candidates[i]);
res.push_back(a);
}
}
return res;
}
};
我们也可以用迭代的解法来做，建立一个三维数组 dp，这里 dp[i] 表示目标数为 i+1 的所有解法集合。这里的i就从1遍历到 target 即可，对于每个i，都新建一个二维数组 cur，然后遍历 candidates 数组，如果遍历到的数字大于i，说明当前及之后的数字都无法组成i，直接 break 掉。否则如果相等，那么把当前数字自己组成一个数组，并且加到 cur 中。否则就遍历 dp[i - candidates[j] - 1] 中的所有数组，如果当前数字大于数组的首元素，则跳过，因为结果要求是要有序的。否则就将当前数字加入数组的开头，并且将数组放入 cur 之中即可，参见代码如下：
解法三：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<vector<int>>> dp;
sort(candidates.begin(), candidates.end());
for (int i = 1; i <= target; ++i) {
vector<vector<int>> cur;
for (int j = 0; j < candidates.size(); ++j) {
if (candidates[j] > i) break;
if (candidates[j] == i) {cur.push_back({candidates[j]}); break;}
for (auto a : dp[i - candidates[j] - 1]) {
if (candidates[j] > a[0]) continue;
a.insert(a.begin(), candidates[j]);
cur.push_back(a);
}
}
dp.push_back(cur);
}
return dp[target - 1];
}
};
到此这篇关于C++实现LeetCode(39.组合之和)的文章就介绍到这了,更多相关C++实现组合之和内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C++实现LeetCode(46.全排列)
[LeetCode] 46. Permutations 全排列 Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 这道题是求全排列问题,给的输入数组没有重复项,这跟之前的那道 Combinations 和类似,解法基本相同
-
C++实现LeetCode(78.子集合)
[LeetCode] 78. Subsets 子集合 Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is:
-
C++实现LeetCode(112.二叉树的路径和)
[LeetCode] 112. Path Sum 二叉树的路径和 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below bi
-
C++实现LeetCode(90.子集合之二)
[LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example
-
C++实现LeetCode(51.N皇后问题)
[LeetCode] 51. N-Queens N皇后问题 The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a di
-
C++实现LeetCode(38.计数和读法)
[LeetCode] 38. Count and Say 计数和读法 The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 is read off as "one 1" or 11. 11 is read off as "two
-
C++实现LeetCode(144.二叉树的先序遍历)
[LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,2,3] Follow up: Recursive solution is trivial, could you do it iterat
-
C++实现LeetCode(113.二叉树路径之和之二)
[LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7
-
C++实现LeetCode(39.组合之和)
[LeetCode] 39. Combination Sum 组合之和 Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may b
-
C++实现LeetCode(40.组合之和之二)
[LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u
-
Java实现LeetCode（组合总和）
leetcode题目 组合总和 -- leetcode 39 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合. 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3
-
C++实现LeetCode(Combinations 组合项)
[LeetCode] Combinations 组合项 Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 这道题让求1到n共n个数字里k个数的组合数的所有情况,还是要用深度优先搜索D
-
基于Python数据结构之递归与回溯搜索
目录 1. 递归函数与回溯深搜的基础知识 2. 求子集 (LeetCode 78) 3. 求子集2 (LeetCode 90) 4. 组合数之和(LeetCode 39,40) 5. 生成括号(LeetCode 22) 6. N皇后(LeetCode 51,52) 7. 火柴棍摆正方形(LeetCode 473) 1. 递归函数与回溯深搜的基础知识 递归是指在函数内部调用自身本身的方法.能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解
-
Python中Collections模块的Counter容器类使用教程
1.collections模块 collections模块自Python 2.4版本开始被引入,包含了dict.set.list.tuple以外的一些特殊的容器类型,分别是: OrderedDict类:排序字典,是字典的子类.引入自2.7. namedtuple()函数:命名元组,是一个工厂函数.引入自2.6. Counter类:为hashable对象计数,是字典的子类.引入自2.7. deque:双向队列.引入自2.4. defaultdict:使用工厂函数创建字典,使不用考虑缺失的字典键.引
-
C++实现LeetCode（三数之和）
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut
-
Java实现LeetCode（两数之和）
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =
-
C++实现LeetCode(18.四数之和)
[LeetCode] 18. 4Sum 四数之和 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be
-
C++实现LeetCode(16.最近三数之和)
[LeetCode] 16. 3Sum Closest 最近三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly on