本文共 2286 字，大约阅读时间需要 7 分钟。

Combination Sum

题目

题目链接：

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]]

分析

题目给出一个包含不重复元素的int类型的数组candidates和一个目标数target。要求从candidates数组中找出所有可能的组合，这些数的和等于target，每个元素可以被多次选中。

可以使用递归的方法来求解这道题。

• 首先，对给出的数组candidates进行升序排序。使用一个count数组记录每一个元素使用的次数。
• 然后遍历整个数组（递归部分）。
  假设当前为第i个元素，为起始元素，希望得到的和为target。
  求出当前元素的最大个数max = target / candidates[i]。
  • 如果max <= 0，由于后面的元素大于当前元素，所以直接return。
  • 否则，不断循环减少max的值，直到为0。
    在每一轮循环中递归求解target = target - candidates[i] * temp，i = i + 1的情况，直到i = candicates.length时停止。
• 每次target为0时，根据count数组和candidates数组，添加当前结果的最终的结果链表中。然后return（由于target为0，后面的元素个数只能为0，所以直接回溯，寻找其他的情况）。

代码如下

class Solution {
       public List
   
    
     > combinationSum(int[] candidates, int target) {
       	List
     
      
       > resultLists = new ArrayList
       
        
         >(); Arrays.sort(candidates); // 排序 int[] count = new int[candidates.length]; combinationSum0(candidates, target, 0, count, resultLists); return resultLists; } private void combinationSum0(int[] candidates, int target, int start, int[] count, List
         
          
           > resultLists) { if (target == 0) { // 已经完成目标 addList(count, candidates, resultLists); return; } if (start >= candidates.length) { // 超出范围 return; } int temp = candidates[start]; // 数组的最小值 int max = target / temp; // 最多能有几个 if (max <= 0) { // 最多能有0个 return; } for (int i = max; i >= 0; i--) { count[start] = i; combinationSum0(candidates, target - i * temp, start + 1, count, resultLists); } // 因为会回溯，count[start]需要为0 // 但是这这一步没有也没关系。 // 因为在上面的循环中，i最后时0，count[start]一定会被置为0。 count[start] = 0; } // 添加结果到结果链表中 private void addList(int[] count, int[] candidates, List
           
            
             > resultLists) { List
             
               list = new ArrayList
              
               (); for (int i = 0; i < count.length; i++) { for (int j = 0; j < count[i]; j++) { list.add(candidates[i]); } } resultLists.add(list); }}
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://fibmb.baihongyu.com/