【题目】
Given a set of candidate numbers (C) and a target number (T), find all unique combinations inCwhere
the candidate numbers sums toT.
Thesamerepeated number may be chosen fromCunlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1,a2,
… ,ak) must be in non-descending order. (ie,a1≤a2≤
… ≤ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set2,3,6,7
and target7
,
A solution set is:
[7]
[2, 2, 3]
【分析】
基本思路是先排好序,然后每次递归中把剩下的元素一一加到结果集合中,并且把目标减去加入的元素,然后把剩下元素(包括当前加入的元素)放到下一层递归中解决子问题。以start记录我们选到了第几个值,并且一直往后选,这样可以避免选到重复的子集。
【代码】
/*********************************
* 日期:2015-01-27
* 作者:SJF0115
* 题目: 39.Combination Sum
* 网址:https://oj.leetcode.com/problems/combination-sum/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// 中间结果
vector<int> path;
// 最终结果
vector<vector<int> > result;
int size = candidates.size();
if(size <= 0){
return result;
}//if
// 排序
sort(candidates.begin(),candidates.end());
// 递归
DFS(candidates,target,0,path,result);
return result;
}
private:
void DFS(vector<int> &candidates, int target,int start,vector<int> &path,vector<vector<int> > &result){
int len = candidates.size();
// 找到一组组合和为target
if(target == 0){
result.push_back(path);
return;
}//if
for(int i = start;i < len;++i){
// 剪枝
if(target < candidates[i]){
return;
}//if
path.push_back(candidates[i]);
DFS(candidates,target-candidates[i],i,path,result);
path.pop_back();
}//for
}
};
int main(){
Solution solution;
int target = 7;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(6);
vec.push_back(7);
vector<vector<int> > result = solution.combinationSum(vec,target);
// 输出
for(int i = 0;i < result.size();++i){
for(int j = 0;j < result[i].size();++j){
cout<<result[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
分享到:
相关推荐
leetcode打不开Leetcode Note Tips Tip1: Two pointer for sorted array (#Array 1. Two Sum) Tip2: Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. Subarray Sum Equals K) Tip3: Knapsack ...
39/Sum.Combination Sum 40/Sum.Combination Sum 2 46.排列(回串) 47/46.排列 2 48.旋转矩阵 49.组字谜 50.(跳过)(坏问题) 53.最大子阵列 54/59.螺旋矩阵 55.跳跃游戏 57.插入间隔 58.(跳过)(Python把戏) 59....
Combination Sum Description 给一组candidates (list of int)和target (int),求使用candidates内数字组合,让总和等于target的所有组合。 candidates内的数字皆不同 candidates内的数字可以重复使用无限次 ...
Leetcode\combination sum(39).swift Leetcode\count number of team(1395).swift Leetcode\counting bits(338).swift Leetcode \find 数组中的所有重复项(442).swift Leetcode\find peak element(162).swift ...
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag 0017 Letter Combinations of a Phone Number Medium 回溯、暴力 0034...
leetcode 2 和 c Leetcode_imp_C Leetcode 在 C 上的实现 大批: leetcode_0001_two_sum.c leetcode_0011_max_area.c leetcode_0015_three_sum.c ...leetcode_0039_combination_sum.c 40 leetcode_0041_first_miss
leetcode Java 246 題目及解答 (英文) Contents 1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder ...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
combinationSum ( self , candidates , target ): def backtrack ( tmp , start , end , target ): if target == 0 : ans . append ( tmp [:]) elif target > 0 : for i in range ( start , end ): tmp . append ( ...
leetcode 2 Useful Links ...Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] [] Slicing Window / Two Pointers [918 Ma
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which...
CombinationSum 组合之和 完成 LinkedList 题目 说明 状态 AddTwoNumber 两数相加 完成 SwapPairs 两两交换链表中的节点 完成 String 题目 说明 状态 LongestSubstring 最长子串 完成 LongestPalindrome 最长回文...
第 296 章PY 和 GO 中的 Leetcode 我在 Python Golang ...Leetcode ...40:combination-sum-ii:传递最后选择的索引 41:先缺失正,交换 42:只是提醒:块 - 垃圾箱 43:多字符串,i+j,i+j+1 44:通配符
def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ result,temp = [],[] self.combinationSumRecu(sorted(candidates),...
Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump Game Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock II Longest...