# 77.Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

## 解法：

public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 0||k<=0||k>n) return res;
return res;
}

public void combineHelper(int n, int k,List<List<Integer>> res,int start,LinkedList<Integer> resTemp){
if (resTemp.size() == k){
return;
}
for(int i=start;i<=n;i++ ){
combineHelper(n,k,res,i+1,resTemp);
resTemp.removeLast();
}
}

public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 0||k<=0||k>n) return res;
return res;
}

public void combineHelper(int n, int k,List<List<Integer>> res,int start,LinkedList<Integer> resTemp){
if (resTemp.size() == k){
return;
}
for(int i=start;i <= n - k+ resTemp.size()+1;i++ ){
combineHelper(n,k,res,i+1,resTemp);
resTemp.removeLast();
}
}

# 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]
]

## 解法一：

public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
return res;
}
public void combinationSumHelper(int[] candidates, int target,List<List<Integer>> res,LinkedList<Integer> tempRes){
if (target < 0) return;
if (0 == target){
}

for (int i = 0;i<candidates.length;i++){
if (tempRes.isEmpty()){
}else {
if(candidates[i]>=tempRes.getLast()){
}else continue;
}
combinationSumHelper(candidates,target-candidates[i],res,tempRes);
tempRes.removeLast();
}
}

## 解法二：

public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
combinationSumHelper(candidates,target,res,new ArrayList<>(),0);
return res;
}

public void combinationSumHelper(int[] candidates, int target,List<List<Integer>> res,ArrayList<Integer> tempRes,int start){
if (target < 0) return;
if (0 == target){
}
for (int i = start;i<candidates.length;i++){
//这里的参数i就代替了解法一里面的if判断
combinationSumHelper(candidates,target-candidates[i],res,tempRes,i);
tempRes.remove(tempRes.size()-1);
}
}

0 条评论

## 相关文章

30750

### 2879 堆的判断

2879 堆的判断 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用...

32580

42770

11730

12420

37570

### LWC 52：687. Longest Univalue Path

LWC 52：687. Longest Univalue Path 传送门：687. Longest Univalue Path Problem: Given...

23970

### Java迭代器Iterator

之前我们实现了迭代器模式，很多编程语言实际上已经内置了迭代器类，比如Java就为我们实现了迭代器Iterator。我们首先来看Iterator中的源码。 通过...

264100

21590

22130