首页 > 代码库 > LeetCode 39. Combination Sum (组合的和)

LeetCode 39. Combination Sum (组合的和)

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

 

For example, given candidate set [2, 3, 6, 7] and target 7
A solution set is: 

[
  [7],
  [2, 2, 3]
]

 

 


题目标签:Array

  题目给了我们一个candidates array 和一个 target, 让我们从array 里找到所有的组合,它的和是等于target的。任何组合只要是它的和等于target的话,都需要找到,但是不需要重复的。这道题中是可以重复利用一个数字的,那么我们就需要每次都代入同一个数字,直到它之和达到target 或者它超过了target, 然后在倒退回去一个数字,继续找下一个数字,这种情况肯定是要用递归了。这里是backtracking,每次倒退回一个数字,需要继续递归下去,在倒退,一直重复直到搜索了所有的可能性。

  我们可以看原题中的例子:

  [2,3,6,7]  target 7

  2                                  选2,sum = 2

  2+2                              选2,sum = 4

  2+2+2                          选2,sum = 6

  2+2+2+2                      选2,sum = 8 这时候 sum已经超出target,需要返回到上一个数字

  2+2+2+3                      选3,sum = 9, 也超出了target, 这里我们可以发现,如果是sorted array的话,从小到大,只要一次超出,后面的数字必然也会超出target,所以可以在第一次超出的时候就直接跳出这一个迭代

  2+2+3                          选3,sum = 7,等于target, 此时返回并且跳出这一个迭代,因为后面的数字肯定超出(array里不会有重复的数字)

  2+3                              选3,sum = 5,小于target,继续递归同一个数字

  2+3+3                          选3,sum = 8,超出target,返回上一个数字

  2+6                              选6,sum = 8,超出target,返回上一个数字

  3                                  选3,这里继续从3开始递归

  ...

  ...

  ...

  我们可以看出,一开始有一个迭代从2,一直到7,然后把每一个数字递归下去,包括它自己,每次递归下去的数字,会继续有一个迭代,一旦超出或者等于了,返回前面一个数字继续递归。所以把array sort一下就可以提早跳出那一轮的迭代。

 

具体看下面代码。

 

Java Solution:

Runtime beats 97.14% 

完成日期:07/16/2017

关键词:Array

关键点:Backtracking with sorted array

 

 1 public class Solution 
 2 {
 3     public List<List<Integer>> combinationSum(int[] candidates, int target) 
 4     {
 5         List<List<Integer>> list = new ArrayList<>();
 6         Arrays.sort(candidates);
 7         backtrack(list, new ArrayList<>(), candidates, target, 0);
 8         
 9         return list;
10     }
11     
12     public static boolean backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start)
13     {
14         if(remain < 0) // if remain is 0 or less than 0, meaning the rest numbers are even greater
15             return false; // therefore, no need to continue the loop, return false
16         else if(remain == 0)
17         {
18             list.add(new ArrayList<>(tempList));
19             return false;
20         }
21         else
22         {
23             for(int i=start; i<nums.length; i++)
24             {
25                 boolean flag;
26                 tempList.add(nums[i]);
27                 flag = backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can use same number.
28                 tempList.remove(tempList.size() - 1);
29                 
30                 if(!flag) // if find a sum or fail to find a sum, there is no need to continue
31                     break;// because it is a sorted array with no duplicates, the rest numbers are even greater.
32             }
33             
34             return true; // return true because previous tempList didn‘t find a sum or fail a sum
35         }
36     }
37 }

参考资料:

https://leetcode.com/problems/combination-sum/#/discuss

 

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

 

LeetCode 39. Combination Sum (组合的和)