【题目】
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations inCwhere
the candidate numbers sums toT.
Each number inCmay only be usedoncein the combination.
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 set10,1,2,7,6,1,5
and target8
,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
【分析】
基本思路是先排好序,然后每次递归中把剩下的元素一一加到结果集合中,并且把目标减去加入的元素,然后把剩下元素(包括当前加入的元素)放到下一层递归中解决子问题。以start记录我们选到了第几个值,并且一直往后选,这样可以避免选到重复的子集。
这一题和上一题:[LeetCode]39.Combination Sum差不多一样的思路,只要稍作修改就行。只要在for循环中加一个判断条件即可:
if(i > start && candidates[i] == candidates[i-1]){
continue;
}//if
这个判断的目的是排除同一层次相同元素的出现。例如:下面例题中有两个1,在第一次递归中不能都出现1,可以的是第一次递归出现1,第二次递归也可以出现一个1
【代码】
/*********************************
* 日期:2015-01-27
* 作者:SJF0115
* 题目: 40.Combination Sum II
* 网址:https://oj.leetcode.com/problems/combination-sum-ii/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > combinationSum2(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(i > start && candidates[i] == candidates[i-1]){
continue;
}//if
// 剪枝
if(target < candidates[i]){
return;
}//if
path.push_back(candidates[i]);
DFS(candidates,target-candidates[i],i+1,path,result);
path.pop_back();
}//for
}
};
int main(){
Solution solution;
int target = 8;
vector<int> vec;
vec.push_back(10);
vec.push_back(1);
vec.push_back(2);
vec.push_back(7);
vec.push_back(6);
vec.push_back(1);
vec.push_back(5);
vector<vector<int> > result = solution.combinationSum2(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 ...
40/Sum.Combination Sum 2 46.排列(回串) 47/46.排列 2 48.旋转矩阵 49.组字谜 50.(跳过)(坏问题) 53.最大子阵列 54/59.螺旋矩阵 55.跳跃游戏 57.插入间隔 58.(跳过)(Python把戏) 59.Spiral Matrix 2(蛮力) ...
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...
239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses 589 244 Reverse Integer 591 245 Palindrome Number 593
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 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
Combination Sum Description 给一组candidates (list of int)和target (int),求使用candidates内数字组合,让总和等于target的所有组合。 candidates内的数字皆不同 candidates内的数字可以重复使用无限次 ...
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 already!) 我经常在递归的结束地方忘记return!!! 题型一:经典暴力递归:(里面涉及到重复不重复的...
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、LeetCode 题解相关文章,至今收获不少好评。此仓库是公众号内容的补充,包括公众号文章涉及到的题目的参考代码,以及 ...
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 ( ...
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 最长回文...
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
Combination Sum II 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 ...
第 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),...