Leetcode 39. Combination Sum 回溯法

题目：

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

 

题意：

给定一个数组，一个目标值，我们需要从数组中挑选数字组成集合，集合中的数字总和要等于目标值。需要找出所有这种集合。

 

 

解法：

这道题我们可以用回溯法来做，首先将数组排序，然后我们可以建立一个类似查找树的方案，然后一直向下查找，直到总和正好达到目标值，记录下结果，然后可以回退一步继续搜索，如果查找过程中总和已经大于了目标值，也进行回退一步。

搜索完毕后就会得到结果 这个和我之前做的一道很像，可以参考一下思路：

https://blog.csdn.net/Lin_QC/article/details/89186436  Leetcode 78 subset 求子集

 

 

代码：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        for(int i =0;i<candidates.length;i++){
            int sum=0;
            List<Integer> add=new ArrayList<Integer>();
            find(sum,i,target,candidates,res,add,0);
        }
        return res;
    }
    public void find(int sum,int now_location,int          target,int[] candidates ,List<List<Integer>>res,List<Integer>add,int step){
        if(sum+candidates[now_location]==target){
            List<Integer> temp=new ArrayList<Integer>();
            temp.addAll(add);
            temp.add(candidates[now_location]);
            res.add(temp);
            return ;
        }
        else if(sum+candidates[now_location]>target){
            return;
        }
        else{
            add.add(candidates[now_location]);
            sum+=candidates[now_location];
            for(int i=now_location;i<candidates.length;i++){  
                find(sum,i,target,candidates,res,add,step+1);
            }
            add.remove(step);
            return;
        }
    }
}