leetcode39. 组合总和

给定一个无重复元素的数组 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]
]

思路：搜索回溯，代码就像说话一样一看就懂。

  

   

    

     

    
    

     

      import java.util.ArrayList;
     
    
   

    

     

    
    

     

      import java.util.Arrays;
     
    
   

    

     

    
    

     

      import java.util.List;
     
    
   

    

     

    
    

     

      import java.util.Stack;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 private List<List<Integer>> res = new ArrayList<>();
     
    
   

    

     

    
    

     
 private int[] candidates;
     
    
   

    

     

    
    

     
 private int len;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
     
    
   

    

     

    
    

     
 if (residue < 0) {
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (residue == 0) {
     
    
   

    

     

    
    

     

       res.add(new ArrayList<>(pre));
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for (int i = start; i < len; i++) {
     
    
   

    

     

    
    

     

       pre.add(candidates[i]);
     
    
   

    

     

    
    

     

       findCombinationSum(residue - candidates[i], i, pre);
     
    
   

    

     

    
    

     

       pre.pop();
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public List<List<Integer>> combinationSum(int[] candidates, int target) {
     
    
   

    

     

    
    

     
 int len = candidates.length;
     
    
   

    

     

    
    

     
 if (len == 0) {
     
    
   

    

     

    
    

     
 return res;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 this.len = len;
     
    
   

    

     

    
    

     
 this.candidates = candidates;
     
    
   

    

     

    
    

     

       findCombinationSum(target, 0, new Stack<>());
     
    
   

    

     

    
    

     
 return res;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104037258