Mumtaz Fatima's blog
Backtracking - Combination Sum II

Backtracking - Combination Sum II

Using backtracking to solve combination sum II problem.

Mumtaz Fatima's photo
Mumtaz Fatima
·

4 min read

Table of contents

Today I'll try to take a stab at combination sum II using backtracking. This blog will contain the code in Java but the algorithm will pretty much apply to any programming language. In fact, if you like the challenge of it - try converting the Java code into your preferred programming language.

So let's dive straight into it!

Prerequisite Knowledge

What you already need to know to understand this solution:

  • Recursion

  • Data structures like array lists, hash sets, etc.

What is backtracking?

Backtracking is the algorithmic approach of considering all possible combinations to solve a problem (source: Wikipedia). There are different types of backtracking approaches: decision problem, optimization problem, and enumeration problem. I won't be diving deep into the three in this paragraph, but if you're interested you can find the definitions in the appendix of this article.

The general idea for implementation is that we need to consider all possible combinations and we use recursion to achieve that. However, questions have special cases that we need to consider so a basic recursion might not always give you the correct solution.

Problem Statement

Given a collection of candidate, numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Solution

Let's read the problem statement again carefully. Here, we are asked to find 'unique' combinations where all the numbers sum to target.

For example, if you have candidates = [1,2,3,4,1] and your target = 5, then you can have the following combinations [ [1,1,3], [2,3], [4,1] ] but you cannot have something like this[[1,3,1] , [3,2] , [1,4] , [4,1] , [2,3] , [1,1,3] ] because these combinations are duplicated. [1,3,1] is considered a duplicate of [1,1,3]

So what data structure can we use to ensure unique combinations? Yes! It starts with hash and ends with set -- HashSet! In order to obtain a unique combination, we either need to use a hashset or we have to come up with an algorithm that deals with preventing duplicates.

In this solution, we go with the second method - which is preventing duplicates. The reasoning behind not pursuing the first method is that we need to convert the HashSet again to an ArrayList which makes the time complexity increase by an order of log N.

How do you find combinations?

The idea of finding combinations relies on the take or not take method. Which is basically at each index, you can choose to take one number or you can choose not to.

In the case of backtracking it means that you add the number to your list of combinations. Then you call the recursive function. Then you remove the last added number from the combination.

How to prevent duplicates?

The idea is to first sort the candidates array. Once we have the sorted array, at each recursion call we check if the current element is equal to its previous element. If it is, then we no longer use it within our combination and move on to the next recursive call.

Summary: check if candidates[i] == candidates[i-1] (don't forget out of bounds)

How do we know if we've reached the target?

There are two approaches you can take to do so. The first approach is to start the curr_sum = 0 and keep changing it as curr_sum += candidates[i]. This approach could be used but it adds another variable for the stack space to keep track of hence decreasing the stack space.

The other approach is to keep decrementing the target by subtracting candidates[i] such that when it reaches 0, you know that you've found the combination that adds up to the target. This makes you carry one less variable, hence increasing the amount of available stack space.

Summary: decrement target target - candidates[i]

Algorithm

So now we can put together the conditions we've discussed above and write some pseudocode.

function combinationSum2(int[] candidates, int target)
    List<List> result
    sort the candidates
    helper(result, candidates, target, new ArrayList<>(), 0 as current index)

function helper()
    check if target == 0
        add the combination as result
        return

    loop from i = index to candidates.length
        check candidates[i] == candidates[i-1] and skip this iteration if true

        if candidates[i] > target break

        add the candidate to combination
        helper(result, candidates, target - candidates[i], i+1)
        remove the candidate to combination

Now let's translate that into code:

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        helper(result, candidates, target, new ArrayList<>(), 0);
        return result;
    }

    public void helper(List<List<Integer>> result, int[] candidates, int target, List<Integer> curr, int index){
        if(target==0){
            result.add(new ArrayList<>(curr));
            return;
        }

        for(int i = index; i< candidates.length; i++){
            if(i > index && candidates[i]==candidates[i-1]){
                continue;
            }
            if(candidates[i] > target){
                break;
            }
            curr.add(candidates[i]);
            helper(result, candidates, target - candidates[i], curr, i + 1);
            curr.remove(curr.size()-1);   
        }
    }
}
leetcode