I'm working on the following problem: Given an array of integers and a sum B, find all unique combinations in the array where the sum is equal to B. The same number may be chosen from the array any number of times to make B.

Note:

1. All numbers will be positive integers.
2. Elements in a combination (a1, a2, …, ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
3. The combinations themselves must be sorted in ascending order. Example:

Input:
N = 4
arr[] = {7,2,6,5}
B = 16

Output:
(2 2 2 2 2 2 2 2)
(2 2 2 2 2 6)
(2 2 2 5 5)
(2 2 5 7)
(2 2 6 6)
(2 7 7)
(5 5 6)

The problem is for the input arr[] = {8, 1, 8, 6, 8}, B = 12 I am getting (1 1 1 1 1 1 1 1 1 1 1 1)(1 1 1 1 1 1 6)(1 1 1 1 8)(1 1 1 1 8)(1 1 1 1 8)(6 6) as output but the correct output is (1 1 1 1 1 1 1 1 1 1 1 1)(1 1 1 1 1 1 6)(1 1 1 1 8)(6 6)

My code:

static void findCombination(int idx, int target, int[] arr, ArrayList<ArrayList<Integer>> ans, List<Integer> ds){
        //base case
       
        if(idx == arr.length){
            if(target == 0){
                ans.add(new ArrayList<>(ds));
            }
            return;
        }
        //recursion
        if(arr[idx] <= target){
            ds.add(arr[idx]);
            findCombination(idx,target-arr[idx],arr,ans,ds); //function call
            ds.remove(ds.size()-1); //backtracking step
        }
        findCombination(idx 1,target,arr,ans,ds);
    }
    //Function to return a list of indexes denoting the required 
    //combinations whose sum is equal to given number.
    static ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int B)
    {
        // add your code here
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int[] arr = new int[A.size()];
        int i = 0;
        for(int val : A){
            arr[i  ] = val;
        }
        Arrays.sort(arr);
        findCombination(0, B, arr, ans, new ArrayList<>());
        return ans;
    }
}

CodePudding user response：

You should be dealing with unique values.

static ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> A, int B) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    findCombination(0, B,
        A.stream().mapToInt(Integer::intValue).distinct().sorted().toArray(),
        ans, new ArrayList<>());
    return ans;
}

CodePudding user response：

You can use a Set or Hashset instead of the ArrayList. It will provide you with unique results only.