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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄