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

Combination_Sum2.java

//https://leetcode.com/problems/combination-sum/
//模版思路 解法

public class Solution {
    public static List<List<Integer>> result = new ArrayList<List<Integer>>();
	public static int[] path = new int[100];
	public static int len = 0;

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		result.clear();
		int idx = 0;
		robot(idx, candidates, target);

		return result;
	}

	private void robot(int idx, int[] candidates, int target) {
		if(target == 0) {//chose end
			//ans
			List<Integer> tmp = new ArrayList<Integer>();
			for (int i = 0; i < len; i++) {
				tmp.add(path[i]);
			}
			result.add(tmp);
			return;
		}
		if(idx >= candidates.length || target < 0) return;//no ans fill
		
		//use
		path[len] = candidates[idx];
		++len;
		robot(idx, candidates, target - candidates[idx]);
		--len;
		//not use
		robot(idx + 1, candidates, target);
	}
}