Combination Sum Debugging

user_13794301 0
Viewed 104

I have written some code to try to solve this challenge, but its not working, i can't seem to figure out where it went wrong, i can find the answer online but that's not the point i'm trying to see why my code doesn't work.

question:

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

this is what i have came up with:

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res,new ArrayList<Integer>(), candidates,target,0,0);
        return res;
    }
    //current = current sum, we want it to be target
    //start is index we are at and where the for loop starts

    public void helper(List<List<Integer>> res, List<Integer> temp, int[] nums, int target, int current, int start){
        if(start>=nums.length){
            return;
        }
        if(current>=target){
            if(current==target){
                res.add(new ArrayList<>(temp));
            }
            temp.remove(temp.size()-1);
            helper(res,temp,nums,target,current-nums[start],start+1);
            return;
        }
        for(int i=start; i<nums.length; i++){
            temp.add(nums[i]);
            helper(res,temp,nums,target,current+nums[i],start);
        }
    }
    
}

explanation of my code:

so i am trying to use recursion backtracking here. i keep for looping an element in the array till the sum is >= target.if its >target i remove the last element since that made it bigger than target and try the other ones. if its = target i add it to result and i remove last element to try find more combinations.

but apparently i am getting error in this line:

temp.remove(temp.size()-1); //saying index out of bounds i am trying to remove when arraylist is empty

so it isnt running how i thought, because if the list is empty current should be 0 and it should even enter that if loop and should never be removed but it is and i am not sure why.

thanks.

backtracking recursion arrays java
2 Answers

The main issue if from trying to roll back the current variable value and call the helper method again from there in the if(current>=target) if statement. You can use the for loop to automatically do that for you and remove the added number after it returns. Then using the functions return to update the start value so that it will continue from where you left off will eliminate duplicates.

And because of the for loop num[i] will never go out of bounds so you dont have to worry about

if(start>=nums.length){
            return;
        }

This is the working version using your solution method

public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    helper(res,new ArrayList<Integer>(), candidates,target,0,0);
    return res;
}

public static int helper(List<List<Integer>> res, List<Integer> temp, int[] nums, int target, int current, int start){

    if(current>=target){
            
        if(current==target){
            res.add(new ArrayList<>(temp));
        }
        return start + 1;
    }
    for(int i=start; i<nums.length; i++){
        temp.add(nums[i]);
        start = helper(res,temp,nums,target,current+nums[i],start);
        temp.remove(temp.size()-1);
    }
    return start;
}

Running the code:

public static void main(String []args){
        List<List<Integer>> res = combinationSum(new int[] {2,3,6,7}, 7);
        System.out.println(res);
}

Result:

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

Try this.

static List<List<Integer>> combinationSum(int[] candidates, int target) {
    int size = candidates.length;
    List<List<Integer>> result = new ArrayList<>();
    new Object() {
        void search(int index, int sum, List<Integer> selected) {
            if (index >= size) {
                if (sum == target)
                    result.add(new ArrayList<>(selected));
            } else {
                int candidate = candidates[index];
                List<Integer> nextSelected = new ArrayList<>(selected);
                for (int nextSum = sum; nextSum <= target; nextSum += candidate, nextSelected.add(candidate))
                    search(index + 1, nextSum, nextSelected);
            }
        }
    }.search(0, 0, new ArrayList<>());
    return result;
}

and

int[] candidates = {2, 3, 6, 7};
int target = 7;
List<List<Integer>> result = combinationSum(candidates, target);
System.out.println(result);

result:

[[7], [2, 2, 3]]
Admin1
Related