Combination Sum

This is a problem in leetcode.

To solve this problem, I decide to use recursion on it:

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> rec = new ArrayList<Integer>();

        search( candidates, target, res, rec, 0);

        return res;
    }

    private void search(int[] arr, int tar, List<List<Integer>>res, List<Integer>rec, int start){

        // check 
        if(tar == 0){
            System.out.println("Added to answer");
            System.out.println("Now rec is: " + rec);
            res.add(rec);
            System.out.println("Now res is: " + res);
            return;
        }

        // for loop
        for( int i = start; i < arr.length; i++ ){
            System.out.println("The element is: " + arr[i]);
            // check if current element > target
            if(arr[i] > tar){
                System.out.println("Break");
                break; // should use break to skip this round
            }

            // if not, then add this element to our rec
            System.out.println("Added to rec");
            rec.add(arr[i]);

            System.out.println("Rec call");
            search(arr, tar - arr[i], res, rec, i);

            System.out.println("Remove current element");
            int test = rec.get(rec.size()-1);
            System.out.println("Kick out: " + test);
            rec.remove(rec.size()-1);

        }

        //System.out.println("Finally, the res is: " + res);
        // return res;
    }
}

Code above has some bugs to fix, but I want to explain my main thought first.
I crate two ArrayList, one is rec for temporary result, and res for final result.
In recursion function search, I will check the value of target first, if it equal to 0, I will add my rec to res, which means I have found the result.
Otherwise, i will check each element in array and sum them up till the sum trigger the condition I mention above.
Unfortunately, I still have two bugs here.
First one is more obviously, that is I need to sort the array first.
Second one is that I can’t add my rec directly, I should use new ArrayList<>(rec). The reason is that I should crate a new independence ArrayList to store my current rec and protect it from being modified later.
Here is a reference link.

And the final version is below:


class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        Arrays.sort(candidates);

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> rec = new ArrayList<Integer>();

        search( candidates, target, res, rec, 0);

        return res;
    }

    private void search(int[] arr, int tar, List<List<Integer>>res, List<Integer>rec, int start){

        // check 
        if(tar == 0){

            res.add(new ArrayList<>(rec));

            return;
        }

        // for loop
        for( int i = start; i < arr.length; i++ ){

            // check if current element > target
            if(arr[i] > tar){

                break; // should use break to skip this round
            }

            // if not, then add this element to our rec

            rec.add(arr[i]);

            search(arr, tar - arr[i], res, rec, i);

            int test = rec.get(rec.size()-1);

            rec.remove(rec.size()-1);

        }

        //System.out.println("Finally, the res is: " + res);
        // return res;
    }
}

Leave a Reply to Anonymous Cancel reply