LeetCode #39: Combination Sum

LeetCode Solutions

https://leetcode.com/problems/combination-sum/

Combination Sum is a problem in which we need to find all the unique combinations of numbers from a given array, such that they add up to a given target sum. Each number in the array can be used multiple times to form a combination.

The solution to this problem can be achieved by using the backtracking approach. In backtracking, we try out all possible combinations by taking one element at a time from the array, and check if it adds up to the given target sum. If it does, then we add it to our result array, otherwise, we backtrack and try out another combination.

Here are the steps to solve the problem using backtracking:

  1. Initialize an empty result array to store all the unique combinations.
  2. Define a backtracking function that takes 3 parameters: a. The remaining target sum to be achieved. b. The index of the current element in the array. c. The current path (combination) being formed.
  3. Check if the remaining sum is equal to zero. If yes, then we have found a valid combination. Append the path to the result array and return.
  4. Check if the remaining sum is less than zero. If yes, then this path is invalid. Return.
  5. Iterate through the array from the current index until the end of the array: a. Append the current element to the current path. b. Recursively call the backtracking function with the remaining sum as target – current element, the index as the current index, and the current path. c. Remove the current element from the current path.
  6. Call the backtracking function with the initial target sum, the index as 0, and an empty path.
  7. Return the result array.

Here is the solution code in Python:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        def backtracking(rem, ind, path):
            if rem == 0:
                res.append(list(path))
                return
            elif rem < 0:
                return
            for i in range(ind, len(candidates)):
                curr = candidates[i]
                path.append(curr)
                backtracking(rem-curr, i, path)
                path.pop()
        backtracking(target, 0, [])
        return res

Time and Space complexity

The time complexity of the solution is dependent on the input size and the number of possible solutions. The algorithm has to explore all possible combinations of candidates that add up to the target. Since each candidate can be used multiple times, the number of recursive calls grows exponentially with the target sum.

The time complexity is O(k * 2^n) where k is the average length of the combinations, and n is the number of elements in the candidates array. This is because each recursive call takes O(k) time, and there are 2^n possible combinations. In the worst case scenario, where all combinations are valid, the time complexity would be O(2^n).

The space complexity is also dependent on the number of solutions, and can be up to O(k * 2^n) since each combination can have a length of up to k. This is because the algorithm is recursively building up the combinations using a path list, and the resulting combinations are stored in the res list. However, since the path list is being reused in each recursive call, the maximum space used by the algorithm is still O(k * n).