Start learning free

LESSON 366 OF 573 · BACKTRACKING

Combination Sum II in Scala: Backtracking Without Duplicates

Practice O(n · 2n) Read the full explanation

Given an array of integers candidates, which may contain duplicates, and an integer target, return every distinct combination of candidates that adds up to target.

Each candidate may be used at most once in a combination, so a number that appears twice in candidates can appear up to twice in one combination. Two combinations are the same when they hold the same numbers the same number of times, whichever copies of a repeated number they use: in [1,1,7] with target = 8, the first 1 with the 7 and the second 1 with the 7 are one combination, [1,7], and it must appear only once.

Write the numbers of each combination in ascending order, and return the combinations in lexicographic order: compare two combinations number by number, and the first position where they differ decides which one comes first. This is the order in which the search described in the note below finds them. If no combination adds up to target, return an empty array.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: Sorted, the candidates are [1,1,2,5,6,7,10]. [1,1,6] uses both 1s.
[1,7] can be made with either 1, but it is listed once. [1,2,5] comes before [1,7] because at the second number, 2 is smaller than 7.

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Explanation: There are three 2s; [1,2,2] uses two of them and appears once. 5 alone is 5.

Example 3:

Input: candidates = [2,3], target = 4
Output: []
Explanation: 2 + 3 = 5 is too much, and the 2 can't be used twice, so no combination adds up to 4.

 

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Note:

The tutorial uses backtracking, as in Combination Sum. Sort candidates. A call gets start, the first index it may still use, remaining, what the combination still needs, and current, the combination built so far. When remaining is 0, it saves a copy of current. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], calls itself with i + 1 and remaining - candidates[i], and removes the number again. Because the candidates are sorted, the loop can stop at the first one that is bigger than remaining.

Two things change from Combination Sum. First, the deeper call starts at i + 1, not at i: there, a number could be chosen again and again; here, each candidate is used at most once. Second, as in Subsets II, the loop skips candidates[i] when i > start and it equals candidates[i - 1]. Inside one call, every turn of the loop picks a different next number, and a second copy of the same value would build exactly the same combinations again. A copy is still taken when it is the first one this call tries, at i = start: that is how [1,1,6] gets its second 1.

The search is exponential: with n candidates, there are at most 2n ways to pick some of them, and copying a combination takes up to n steps, so the time is O(n · 2n) in the worst case. The sorted order keeps it far smaller in practice: the calls only build distinct combinations whose sum is at most target. Besides the answer, the extra space is O(n): the combination being built and one call per number in it.

STEP 1 OF 13
    Ctrl + Enter to check

    SCALA · BACKTRACKING

    Combination Sum Ii in Scala, explained

    Problem overview

    The method combinationSum2 receives candidates, an Array[Int] that may contain repeated numbers, and a target. It returns every distinct combination of candidates that adds up to target, as a List[List[Int]]. Each candidate can be used at most once, so a number that appears twice in the array can appear up to twice in a combination.

    Two combinations are the same when they hold the same numbers the same number of times, whichever copies they use. In [1,1,7] with target = 8, the first 1 with the 7 and the second 1 with the 7 are the same combination, [1,7], and it is listed once. The numbers of each combination are in ascending order, and the combinations are in lexicographic order. When nothing adds up to the target, the result is an empty list.

    For [10,1,2,7,6,1,5] with target = 8 the answer is List(List(1, 1, 6), List(1, 2, 5), List(1, 7), List(2, 6)). For [2,3] with target = 4 it is empty: 2 + 3 is 5, and the 2 can't be used twice.

    Approach: sorted backtracking with a skip rule

    Trying every subset of the candidates and summing it would take up to 2^n subsets with up to 100 candidates, and it would still need a way to drop repeated combinations. Backtracking builds combinations one number at a time and abandons a partial combination as soon as it can't succeed.

    First sort candidates. Sorting makes equal numbers neighbours, gives the required order, and allows an early stop: once a candidate is bigger than what the combination still needs, every later one is bigger too.

    A call receives start, the first index it may use, remaining, how much the combination still needs, and current, the combination so far. When remaining is 0, the combination is complete and a copy is saved. Otherwise a loop tries each index i from start as the next number: add candidates(i), call again with i + 1 and remaining - candidates(i), then remove the number.

    Two details separate this from the version where numbers may be reused. The recursive call starts at i + 1 rather than at i, so a candidate is used at most once. And the loop skips candidates(i) when it equals candidates(i - 1) and i > start: this call already tried that value as its next number, so a second copy would build the same combinations again. The copy at i == start is still taken, which is how [1,1,6] gets its second 1.

    Step by step

    1. Sort candidates in place with scala.util.Sorting.quickSort(candidates).
    2. Create result, an empty ArrayBuffer[List[Int]]().
    3. Start the search with backtrack(candidates, 0, target, ArrayBuffer[Int](), result): nothing chosen, all of the target still needed.
    4. Return result.toList as the last expression.
    5. Write the helper backtrack with the array, start, remaining, current and result, returning Unit.
    6. Check for a complete combination: if (remaining == 0).
    7. Save a copy and return. result += current.toList stores a snapshot. All candidates are at least 1, so adding more would overshoot the target, and the call can end.
    8. Open a breakable block and, inside it, a for loop with i over start until candidates.length. Scala has no built-in break; break() jumps to the end of the breakable block.
    9. Skip repeats with if (i == start || candidates(i) != candidates(i - 1)). Scala has no continue either, so the rest of the body goes inside this if.
    10. Stop early: if candidates(i) > remaining, call break(). The array is sorted, so no later number fits.
    11. Choose the number: current += candidates(i).
    12. Recurse with i + 1 and remaining - candidates(i).
    13. Undo with current.remove(current.length - 1).

    The solution in Scala

    class Solution {
    def combinationSum2(candidates: Array[Int], target: Int): List[List[Int]] = {
        scala.util.Sorting.quickSort(candidates)
        val result = ArrayBuffer[List[Int]]()
        backtrack(candidates, 0, target, ArrayBuffer[Int](), result)
        result.toList
    }

    def backtrack(candidates: Array[Int], start: Int, remaining: Int, current: ArrayBuffer[Int], result: ArrayBuffer[List[Int]]): Unit = {
        if (remaining == 0) {
            result += current.toList
            return
        }
        breakable {
            for (i <- start until candidates.length) {
                if (i == start || candidates(i) != candidates(i - 1)) {
                    if (candidates(i) > remaining) {
                        break()
                    }
                    current += candidates(i)
                    backtrack(candidates, i + 1, remaining - candidates(i), current, result)
                    current.remove(current.length - 1)
                }
            }
        }
    }
}

    Scala details worth a look:

    • breakable and break() come from scala.util.control.Breaks. They are ordinary library code: break() throws a control exception that the enclosing breakable catches. In a file of your own, add import scala.util.control.Breaks.*.
    • break() leaves the loop, not the call. After the breakable block ends, the method returns normally to its caller, which then removes its own number and tries the next one.
    • current.toList is a snapshot. The buffer keeps changing during the search, and the list is a copy of its numbers at that moment.
    • remove(index) takes an index, not a value, so removing the last number uses current.length - 1.
    • The return inside if (remaining == 0) is a plain return from the method. It is outside the breakable block, so it does not interfere with break().
    • quickSort sorts the caller's array in place, as in the lesson.

    Complexity

    Time: O(n * 2^n) in the worst case, where n is the number of candidates: at most 2^n ways to pick some of them, and a copy takes up to n steps. In practice it is far smaller, because the search only extends combinations that are distinct and whose sum is at most target, and it stops at the first candidate that is too big.

    Space: O(n) beyond the answer: the combination being built and one call per number in it.

    Edge cases and common mistakes

    • Recursing with i instead of i + 1. That allows reusing a number. For [2,3] with target 4 it returns List(List(2, 2)) instead of an empty list.
    • No duplicate skip. For [1,1,7] with target 8 the result is List(List(1, 7), List(1, 7)): the same combination twice. The correct result is List(List(1, 7)).
    • Skipping with i == 0 instead of i == start. Then a repeated number is skipped even when it is the first choice of its call. For [1,1,6] with target 8 the result is empty, because [1,1,6] needs both 1s.
    • No combination. [2,3] with target 4 gives an empty list.
    • A candidate equal to the target. [3] with target 3 gives List(List(3)).
    • Not sorting. The early break() and the neighbour comparison both rely on sorted input.

    Testing

    • [10,1,2,7,6,1,5], target = 8 gives List(List(1, 1, 6), List(1, 2, 5), List(1, 7), List(2, 6)).
    • [2,5,2,1,2], target = 5 gives List(List(1, 2, 2), List(5)).
    • [2,3], target = 4 gives List().
    • [1,1,7], target = 8 gives List(List(1, 7)).
    • [3], target = 3 gives List(List(3)).
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free