_40. Combination Sum II.md

40. Combination Sum II

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 13, 2024

Last updated : August 13, 2024

---

Related Topics : Array, Backtracking

Acceptance Rate : 57.25 %

---

Solutions

• m40.py

Python

m40.py

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # sort since if we add an index and it's greater,
        # then adding any index past that will also be greater
        candidates.sort()

        def helper(currTotal: int = 0,
                   currIndx: int = 0, 
                   valsSoFar: List[int] = [],
                   output: List[int] = []) -> List[int] :
            if currTotal == target :
                output.append(valsSoFar.copy())
                return output

            if currTotal > target :
                return output

            # Iterate through each next potential value till too big
            while currIndx < len(candidates) and candidates[currIndx] + currTotal <= target :
                # To avoid repeat combinations, jump past the group of same values
                startIndx, endIndx = currIndx, currIndx
                while endIndx < len(candidates) and candidates[endIndx] == candidates[startIndx] :
                    endIndx += 1

                for i in range(startIndx, endIndx) :
                    if currTotal + candidates[currIndx] > target :
                        break
                    valsSoFar.append(candidates[currIndx])
                    currTotal += candidates[currIndx]
                    helper(currTotal, endIndx, valsSoFar, output)

                # Remove the values since we're using the same valsSoFar pointer
                while valsSoFar and valsSoFar[-1] == candidates[currIndx] :
                    currTotal -= valsSoFar.pop()

                currIndx = endIndx
            return output

        return helper()