2020-10-04

/** * 39. 组合总和 * @author wsq * @date 2020/10/04 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ] 示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ] 链接：https://leetcode-cn.com/problems/combination-sum */ package com.wsq.huishuo; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CombinationSum { List<List<Integer>> ans = new ArrayList<>(); List<Integer> targetList = new ArrayList<>(); /** * 回溯法 * @param candidates * @param target * @return */ public List<List<Integer>> combinationSum(int[] candidates, int target) { if(candidates.length == 0) { return ans; } Arrays.sort(candidates); findTargetList(candidates, 0, target); return ans; } /** * 寻找目标序列 * @param candidates * @param target */ private void findTargetList(int[] candidates, int pos, int target) { // TODO Auto-generated method stub for(int i = pos; i < candidates.length; ++i) { int tmpN = candidates[i]; if(tmpN == target) { List tmpList = new ArrayList(targetList); tmpList.add(tmpN); ans.add(tmpList); break; }else if(tmpN < target) { targetList.add(tmpN); findTargetList(candidates, i, target - tmpN); targetList.remove(targetList.size() - 1); }else { break; } } } public static void main(String[] args) { int[] candidates = {2,3,6,7}; int target = 7; CombinationSum cs = new CombinationSum(); cs.combinationSum(candidates, target); } }