Recursive Java Solution


#1
public class Solution {
public ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int B) {
    if(A==null || B==0)
        return new ArrayList<ArrayList<Integer>>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    int sum=0;
    Collections.sort(A);
    for(int i=0;i<A.size();i++)
        combinations(A,result, new ArrayList(),i,B,sum);
    return result;
}
public  void combinations(ArrayList<Integer> A, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> temp, int i, int B,int sum){
    temp.add(A.get(i));
    sum+=A.get(i);
    if(sum>B)
        return;
    if(sum == B){
        Collections.sort(temp);
        for(int k=0;k<result.size();k++){
            if(result.get(k).equals(temp))
                return;
        }
        result.add(temp);
        return;
    }
    for(int j=0;j<A.size();j++){
        if((sum+A.get(j))<=B)
            combinations(A,result, new ArrayList<Integer>(temp), j, B, sum);
    }
}

}