Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
主要的思路是这一次是用这个数字还是不用这个数字
import java.util.LinkedList;
import java.util.List;
public class Solution39 {
public static List<List<Integer>> ans = new LinkedList<List<Integer>>();
public static LinkedList<Integer> list = new LinkedList<Integer>();
public static void robot(int idx,int c[],int target){
if (target==0) {
System.out.println(list);
List<Integer> list2 = new LinkedList<Integer>();
for (Integer i : list) {
list2.add(i);
}
ans.add(list2);
return;
}
if (target<0||idx>=c.length) {
return;
}
list.add(c[idx]);
robot(idx, c, target-c[idx]);
list.pollLast();
robot(idx+1, c, target);
}
public static void main(String[] args) {
int arr[]={2, 3, 6, 7};
robot(0, arr, 7);
}
}
