Differencce between the given codes for combination sum problem

Question

Ok, I have been trying to find the mistake in my code or the place where it changes from the given code. There are two codes here code #1-

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(candidates);
      backtrack(list, new ArrayList<>(), candidates, target, 0);
      return list;  
    }
    public void backtrack(List<List<Integer>> list, List<Integer> temp, int[] nums, int remain, int start) {
        if(remain < 0) return;
        else if (remain == 0) list.add(new ArrayList<>(temp));
        else {
            for(int i = start; i < nums.length; i ++) {
                temp.add(nums[i]);
                backtrack(list, temp, nums, remain - nums[i], i);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

code #2-

class Solution {
    public static void combi(int n, int[] arr, int tar, List<List<Integer>> res, List<Integer> opt, int sum){
        if(sum>tar){
            return;
        }else if(sum == tar){
            res.add(new ArrayList<>(opt));
          
        }else{
        for(int i=0;i<n;i++){
             opt.add(arr[i]);
             combi(n, arr, tar, res, opt, sum+arr[i]);
             opt.remove(opt.size()-1);
             
        }}
    }
    public List<List<Integer>> combinationSum(int[] arr, int tar) {
       List<List<Integer>> res = new ArrayList<>();
       Arrays.sort(arr);
       combi(arr.length, arr, tar, res, new ArrayList<>(), 0);
       return res; 
    }

code 2 is written by me now i want to know why the code1 is giving only the unique sol'n when i believe it should give all the possible sol'n, duplicates too as my code gives. I dont get it can you please tell me what is the difference.

so the test case is

[2,3,6,7]

and my code gives your text [[2,2,3],[2,3,2],[3,2,2],[7]]

type here

but the code gives

[[2,2,3],[7]]

One thing I can do is use set to get the unique sol'n but what ever the first code does is much easier I just don't get why the code give unique sol'ns only.

Do not tag this as dsa. The dsa tag is for Digital Signature Algorithm. — PaulMcKenzie
– PaulMcKenzie, Commented Oct 20, 2023 at 13:42

Sash Sinha · Accepted Answer · 2023-10-20 07:34:45Z

0

The key difference between the two codes is the start parameter in backtrack() method of code #1, which ensures you only move forward or stay at the current element when making recursive calls. This avoids permutations of the same combination without needing a Set for deduplication.

In code #1: backtrack(list, temp, nums, remain - nums[i], i);
Notice the i in the recursive call. This ensures you reuse the current number or use numbers that come after it, avoiding duplicates.
In code #2: combi(n, arr, tar, res, opt, sum+arr[i]);
There's no such constraint. You always start from i=0, leading to permutations of the same combination.

answered Oct 20, 2023 at 7:34

Sash Sinha

22.8k4 gold badges27 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Differencce between the given codes for combination sum problem

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related