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] ]
题意：
给定一个集合以及一个值target，找出所有加起来等于target的组合。（每个元素可以用无数次）
Solution1: Backtracking
code:
1 /* 2 Time: O(n!) factorial, n！=1×2×3×…×n 3 Space: O(n) coz n levels in stack for recrusion 4 */ 5 6 class Solution { 7 public List<List<Integer>> combinationSum(int[] nums, int target) { 8 Arrays.sort(nums); // 呼应dfs的剪枝动作 9 List<List<Integer>> result = new ArrayList<>(); 10 List<Integer> path = new ArrayList<>(); 11 dfs(nums, path, result, target, 0); 12 return result; 13 } 14 15 private static void dfs(int[] nums, List<Integer> path, 16 List<List<Integer>> result, int remain, int start) { 17 // base case 18 if (remain == 0) { 19 result.add(new ArrayList<Integer>(path)); 20 return; 21 } 22 23 for (int i = start; i < nums.length; i++) { 24 if (remain < nums[i]) return; //基于 Arrays.sort(nums); 25 path.add(nums[i]); 26 dfs(nums, path, result, remain - nums[i], i); 27 path.remove(path.size() - 1); 28 } 29 } 30 }
转载于:https://www.cnblogs.com/liuliu5151/p/10705497.html
