(回溯法)LeetCode#39. Combination Sum

xiaoxiao2021-02-28  41

题目:给定一个整型数组(不包括重复元素)和一个int类型的target,找出能组合等于target的所有组合,返回列表

例如数组为[2, 3, 6, 7],target的值为7,返回值为 [ [7], [2, 2, 3] ] 思路:通过回溯法,往前寻找解,达到结束条件就返回一步(这里的结束条件有两个:remain小于0或者remain等于0,等于0的时候找到了其中一个解)难度:Medium代码: public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(candidates == null || candidates.length == 0){ return result; } Arrays.sort(candidates); if(target < candidates[0]){ return result; } helper(result,candidates,0,target,new ArrayList<>()); return result; } private void helper(List<List<Integer>> result, int[] candidates, int pos, int remain,List<Integer> list){ if(remain < 0){ return; }else if(remain == 0){ result.add(new ArrayList<>(list));//将其中一个解加入到列表 }else{ for(int i = pos; i < candidates.length; i++){ list.add(candidates[i]); helper(result, candidates, i, remain-candidates[i], list); list.remove(list.size()-1);//返回一步 } } } }
转载请注明原文地址: https://www.6miu.com/read-77657.html

最新回复(0)