Backtracking, Scenarios/Observations/Thoughts
Kyle Ingram
119

Hi All,

When working on backtracking problems, I came across a couple that were dependant on the starting index.

My question is, how do you recognize that our function will need to key off the startIdx and when to use 0, idx, or idx+1 when we recursively call our backtrack function?
I made a couple notes of what I believe the startIdx are used for but would like to know what others' think.

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmpList = new ArrayList<>();
        
        backtrack(candidates, target, tmpList, res,0);
        return res;
    }
    public static void backtrack(int[] candidates, int target, List<Integer> tmpList, List<List<Integer>> res, int start){
    if(target < 0) {
        return;
    } else if(target==0) {
        res.add(new ArrayList(tmpList));
    } else { 
    for(int i=start;i<candidates.length;i++){
        //explore
        tmpList.add(candidates[i]);
        //backtrack if you leave start at 0 you get duplicates [[2,2,3],[2,3,2],[3,2,2]] use as many elements as you want 
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 3, 1], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 3, 1], [2, 3, 2], [2, 3, 3], [3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 3, 1], [3, 3, 2], [3, 3, 3]]

        //if you leave it as i you are able to reuse elements from array up to nums.length times so if you see 1,2,3 you won’t see 3, 2,1 but can still reuse elements 
[[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]]

        //if you leave it as i+1 you only use distinct elements once
        //1,2,3
        backtrack(candidates, target-candidates[i], tmpList, res,i);
        //remove
        tmpList.remove(tmpList.size()-1);
    }
    } 
    }
    
}

Thanks!

Comments (0)