Start learning free

LESSON 356 OF 540 · BACKTRACKING

Combination Sum in Scala: Backtracking with a Sorted Array

Practice O(nt/m) Read the full explanation

Given an array of distinct integers candidates and an integer target, return every combination of numbers from candidates that adds up to target.

The same number may be chosen any number of times. Two combinations are the same when they use the same numbers the same number of times, whatever the order: [2, 2, 3] and [3, 2, 2] are one combination, 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. If no combination adds up to target, return an empty array.

 

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 + 2 + 3 = 7, using the 2 twice, and 7 alone is 7.
No other combination adds up to 7. [2,2,3] comes first because its first number, 2, is smaller than 7.

Example 2:

Input: candidates = [5,2,3], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: The candidates are not sorted, but every combination is written in ascending order.
[2,2,2,2] and [2,3,3] both start with 2; at their second number, 2 is smaller than 3. [3,5] starts with 3, so it comes last.

Example 3:

Input: candidates = [2], target = 1
Output: []
Explanation: The only candidate, 2, is already bigger than 1, so no combination adds up to 1.

 

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All the numbers in candidates are distinct.
  • 1 <= target <= 40

Note:

The tutorial uses backtracking. Sort candidates, then build a combination one number at a time: try every candidate from the position of the last number chosen onward (that same number included, since numbers can repeat), go deeper with what is left of target, then remove the number again and try the next one. Starting from the last chosen position builds each combination exactly once, already in ascending order, and the combinations come out in lexicographic order. Because the candidates are sorted, the loop can stop at the first one that is bigger than what is left.

The search is exponential: with n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each of them is one of n candidates, so the time is O(nt/m) in the worst case. Besides the answer, the extra space is O(t / m): the combination being built and one call per number in it.

STEP 1 OF 12
    Ctrl + Enter to check

    SCALA · BACKTRACKING

    Combination Sum in Scala, explained

    Problem overview

    The method combinationSum gets an Array[Int] of distinct numbers, candidates, and a target. It returns every combination of candidates that adds up to target, as a List[List[Int]]. A number can be used any number of times. Two combinations are the same when they use the same numbers the same number of times, so [2, 2, 3] and [3, 2, 2] count once. Each combination is written in ascending order, and the combinations are listed in lexicographic order: compare number by number, and the first difference decides.

    For candidates = [2, 3, 6, 7] and target = 7, the answer is [[2, 2, 3], [7]]. For [5, 2, 3] and target 8 it is [[2, 2, 2, 2], [2, 3, 3], [3, 5]], even though the input isn't sorted. For [2] and target 1 it is empty.

    Approach: build one number at a time

    There is no formula for this: the answer has to be searched for. Backtracking does it by building a combination one number at a time. At each step, pick a candidate, subtract it from what is still needed, and ask the same question for the smaller amount. When the amount reaches exactly 0, the numbers chosen form a valid combination. Then undo the last choice and try the next candidate.

    Two details keep the search small and the output correct:

    • Only move forward in the sorted array. If a call is allowed to pick any candidate at any depth, it finds [2, 2, 3], [2, 3, 2] and [3, 2, 2], which are one combination. Sorting candidates first and letting each call start at the index of the last number chosen, not at 0, makes every combination appear once, in ascending order. Starting at that same index, not the next one, lets a number repeat.
    • Stop early. With the candidates sorted, once candidates(j) is bigger than what remains, every later candidate is bigger too, so the loop can stop.

    Because the first number varies slowest, the combinations come out already in lexicographic order, with no sorting of the result.

    The cost is exponential. A combination has at most t / m numbers, where t is the target and m the smallest candidate, and each is one of n candidates, so the time is O(n^(t/m)) in the worst case. Pruning with the sorted order cuts much of that in practice.

    Step by step

    combinationSum

    1. Sort the candidates in place with scala.util.Sorting.quickSort(candidates). This is what gives the ascending combinations, the lexicographic order of the result and the early stop.
    2. Create result, an empty ArrayBuffer[List[Int]], to collect the combinations. Each combination is a list, so the buffer holds lists.
    3. Start the search with all of target still needed, index 0 as the first usable candidate, an empty ArrayBuffer[Int] as the combination so far, and result.
    4. Return result.toList, the buffer converted to the List the method promises.

    backtrack

    1. Declare the helper with the candidates, remaining (what the combination still needs), i (the first index it may use), current (the combination built so far) and result. It returns Unit: it reports its findings by adding to result.
    2. Check for success: if remaining == 0, the numbers in current add up to the target.
    3. Save a snapshot: add current.toList to result, then return. The copy matters because current keeps changing as the search goes on. Returning is safe because every candidate is at least 2, so adding more could only overshoot.
    4. Open a loop for j in i until candidates.length. Scala has no break statement, so the loop goes inside a breakable block, and break() jumps to its end.
    5. Stop when a candidate is too big: if candidates(j) > remaining, call break().
    6. Choose it: add candidates(j) to current with +=.
    7. Recurse with remaining - candidates(j) and the same index j, not j + 1, so the number may be used again.
    8. Undo the choice: remove the last element of current with remove(current.length - 1), so the loop can try the next candidate from the same state.

    The solution in Scala

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

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

    The lesson's editor already has the imports this code needs. In a file of your own, add import scala.collection.mutable.ArrayBuffer and import scala.util.control.Breaks.* at the top.

    The Scala details worth noticing:

    • quickSort sorts the array in place. The caller's array changes: after the call, Array(5, 2, 3) holds [2, 3, 5]. It returns Unit, so there is no sorted copy to assign.
    • toList makes a copy. result += current.toList stores an immutable snapshot. Adding current itself would store the same buffer many times, and every stored entry would change with it. After current += 3 on a buffer holding 1 and 2, the buffer shows ArrayBuffer(1, 2, 3) while a snapshot taken earlier stays List(1, 2).
    • remove(n) takes an index. On an ArrayBuffer[Int], remove(current.length - 1) deletes the last element, whatever its value. For ArrayBuffer(2, 2, 3) it leaves ArrayBuffer(2, 2). For a buffer of numbers, -= would instead remove the first element equal to its argument.
    • breakable and break(). They come from scala.util.control.Breaks. break() works by throwing a control exception that the enclosing breakable catches, so the breakable must surround the loop, not sit inside it.
    • i until candidates.length is a range that excludes its end, so j runs over valid indexes only.
    • The last expression is the result. result.toList needs no return.

    Complexity

    Time: O(n^(t/m)) in the worst case, with n candidates, target t and smallest candidate m. The recursion is at most t / m levels deep, and each level can choose among n candidates. Stopping at the first candidate that is too big avoids many branches, and the real work also depends on how many combinations the answer holds, because each one is copied into the result.

    Space: O(t / m) beyond the answer: current holds at most t / m numbers, and the call stack has one frame per number chosen.

    Edge cases and common mistakes

    • No combination. [2] with target 1 returns an empty list: the first candidate is already too big, so the loop breaks at once. [3, 5] with target 7 also returns an empty list, because 3, 5, 6, 8 and 9 skip over 7.
    • Repeated numbers. [2, 3] with target 6 returns [[2, 2, 2], [3, 3]]. Passing j + 1 instead of j would forbid repeats and return an empty list.
    • Unsorted input. [5, 2, 3] must be sorted first. Without sorting, the early break() would stop too soon, and the result would not come out in order.
    • Starting every call at 0. This finds the same combination in every order and fills the answer with duplicates.
    • Storing current instead of a copy. All entries in result would alias one buffer. By the end it is empty, so every entry would be empty too.
    • Forgetting the undo. Without remove, the numbers from one branch stay in current and corrupt the next.
    • Using -= to undo. It removes the first matching value, which for a repeated number is not the one just added.

    Testing

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