public class Solution {
public
ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int
target) {
ArrayList<ArrayList<Integer> > result = new
ArrayList<ArrayList<Integer> >();
Arrays.sort(num);
int
len = num.length;
if(len > 0
&& num[0] <= target){
ArrayList<ArrayListWithSum> alist = new
ArrayList<ArrayListWithSum>();
alist.add(new
ArrayListWithSum(new
ArrayList<Integer>(), 0));
int
index = 0;
while(index < len && !alist.isEmpty()){
ArrayList<ArrayListWithSum> temp = new
ArrayList<ArrayListWithSum>();
int
theSame = checkSame(num, index);
while(!alist.isEmpty()){
ArrayListWithSum temp1 = alist.remove(0);
ArrayList<Integer> toBeAdded = new
ArrayList<Integer>();
for(int
j = 0; j < theSame - index + 1; ++j){
ArrayList<Integer> templist = new
ArrayList<Integer>();
templist.addAll(temp1.li);
templist.addAll(toBeAdded);
if(temp1.sum + j * num[index] < target)
temp.add(new
ArrayListWithSum(templist, temp1.sum + j * num[index]));
else
if(temp1.sum + j * num[index] == target)
result.add(templist);
toBeAdded.add(num[index]);
}
}
alist = temp;
index = theSame;
}
}
return
result;
}
public
static int checkSame(int[] arr, int
i){
int
len = arr.length;
int
j = i;
for(; j < len; ++j){
if(arr[j] != arr[i])
break;
}
return
j;
}
}
class
ArrayListWithSum{
ArrayList<Integer> li;
int
sum;
ArrayListWithSum(ArrayList<Integer> li, int
sum){
this.li = li;
this.sum = sum;
}
}
