leetcode/code/lc39.java at master · mJackie/leetcode · GitHub

40 lines (37 loc) · 1.6 KB

package code;

import java.util.ArrayList;

import java.util.List;

* 39. Combination Sum

* 题意：找出和为sum的所有组合

* 难度：Medium

* 分类：Array, Backtracking

* 思路：回溯法

* Tips：向res添加答案时注意要new一个新的List,否则后续循环的操作会影响res中的L; 设置一个start标志，记录上次数组循环到哪了,防止重复集合。

* 和lc46,lc78做比较，46是排列组合，所以不需要start标志，start标志是为了防止相同元素的组合排列不同而当做了另一种

public class lc39 {

public static void main(String[] args) {

int[] candidates = {2,3,6,7};

int target = 7;

System.out.println(combinationSum(candidates, target).toString());

}

public static List<List<Integer>> combinationSum(int[] candidates, int target) {

List<List<Integer>> res = new ArrayList<List<Integer>>();

if(candidates.length==0||target==0) return res;

List<Integer> l = new ArrayList<Integer>();

backtracking(res,candidates,target,l,0,0);

return res;

}

public static void backtracking(List<List<Integer>> res, int[] candidates, int target, List<Integer> l, int sum, int start){

for (int i = start; i < candidates.length; i++) {

l.add(candidates[i]);

if(sum+candidates[i]==target) {

res.add(new ArrayList<>(l));//new 新的 List

} else if(sum+candidates[i]<target){

backtracking(res, candidates, target, l, sum+candidates[i],i);

}

l.remove((Integer)candidates[i]);

}

Expand file tree