leetcode练习-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]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
再排列组合中，我们的经常套路是回溯+BFS
回溯的过程有借助各种工具进行保存和退格操作
BFS一边都是遍历所有的情况，按照一定的规律，比如从小到大，奇数，偶数，等
BFS函数再结尾时一般要进行退格回溯，保证进入下一结点同层时的正确性。

import java.util.*;
class Solution {
	List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);		//题目是从小到大进行排列的，我们事先要排好序，因为后面的数都是大于等于前面的
        BFS(0,candidates,target,0,new ArrayList<>());
        return list;
    }
	private void BFS(int start,int[] candidates, int target,int val, List l) {//start是上一结点的index，val是list的和
		List<Integer> list2=new ArrayList<>(l);		//将传过来的列表进行深拷贝，因为回溯中有退格操作，不能直接就是引用
		if(val==target)		//找到目标
			list.add(list2);
		for(int i=start;i<candidates.length;i++) {		//从上一层大小往后
			
			int current=candidates[i];							//保存当前结点的值
			if(current+val>target)								//candidates数组都是非负数，所以只要大于就不用继续了
				return ;
			list2.add(candidates[i]);							//加上该结点
			BFS(i,candidates,target,current+val,list2);
			list2.remove(list2.size()-1);						//记得回溯操作的退格，我们还要从下一元素开始操作，记得退格。
		}
	}
	public static void main(String[] agrs) {
		int[] candidates= {2,3,5};
		int target=8;
		List<List<Integer>> list=new Solution().combinationSum(candidates, target);
		for(List<Integer> l:list) {
			for(Integer i:l) {
				System.out.print(i+" ");
			}
			System.out.println();
		}
	}
}