combination_sum_ii

View Source

 1from collections import Counter
 2# @leet start
 3
 4
 5class Solution:
 6    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
 7        """
 8        This question asks us to find the combination sum, but instead of allowing
 9        any number to be used infinitely, each number can only be used once.
10
11        To solve this problem, we can use a counter, since that contains
12        the numbers and counts of each number.
13
14        We dfs as normal as we would in combination sum, but instead of iterating
15        through all the candidates, we iterate through the counter and we check
16        to make sure the counter's value is greater than 1 indicating the number
17        still exists in the counter.
18
19        We then add that number to our list and dfs through the list, and pop
20        and readd the item to the counter to reverse the backtracking.
21        """
22        result = set()
23        counter = Counter(candidates)
24
25        def dfs(total, l):
26            if total > target:
27                return
28
29            if total == target:
30                l = sorted(l)
31                result.add(tuple(l))
32                return
33
34            for val, freq in counter.items():
35                if freq <= 0:
36                    continue
37                counter[val] -= 1
38                l.append(val)
39                dfs(total + val, l)
40                l.pop()
41                counter[val] += 1
42
43        dfs(0, [])
44        return list(result)
45
46
47# @leet end
48
49
50def test():
51    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
 8        """
 9        This question asks us to find the combination sum, but instead of allowing
10        any number to be used infinitely, each number can only be used once.
11
12        To solve this problem, we can use a counter, since that contains
13        the numbers and counts of each number.
14
15        We dfs as normal as we would in combination sum, but instead of iterating
16        through all the candidates, we iterate through the counter and we check
17        to make sure the counter's value is greater than 1 indicating the number
18        still exists in the counter.
19
20        We then add that number to our list and dfs through the list, and pop
21        and readd the item to the counter to reverse the backtracking.
22        """
23        result = set()
24        counter = Counter(candidates)
25
26        def dfs(total, l):
27            if total > target:
28                return
29
30            if total == target:
31                l = sorted(l)
32                result.add(tuple(l))
33                return
34
35            for val, freq in counter.items():
36                if freq <= 0:
37                    continue
38                counter[val] -= 1
39                l.append(val)
40                dfs(total + val, l)
41                l.pop()
42                counter[val] += 1
43
44        dfs(0, [])
45        return list(result)

def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]: View Source

 7    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
 8        """
 9        This question asks us to find the combination sum, but instead of allowing
10        any number to be used infinitely, each number can only be used once.
11
12        To solve this problem, we can use a counter, since that contains
13        the numbers and counts of each number.
14
15        We dfs as normal as we would in combination sum, but instead of iterating
16        through all the candidates, we iterate through the counter and we check
17        to make sure the counter's value is greater than 1 indicating the number
18        still exists in the counter.
19
20        We then add that number to our list and dfs through the list, and pop
21        and readd the item to the counter to reverse the backtracking.
22        """
23        result = set()
24        counter = Counter(candidates)
25
26        def dfs(total, l):
27            if total > target:
28                return
29
30            if total == target:
31                l = sorted(l)
32                result.add(tuple(l))
33                return
34
35            for val, freq in counter.items():
36                if freq <= 0:
37                    continue
38                counter[val] -= 1
39                l.append(val)
40                dfs(total + val, l)
41                l.pop()
42                counter[val] += 1
43
44        dfs(0, [])
45        return list(result)

This question asks us to find the combination sum, but instead of allowing any number to be used infinitely, each number can only be used once.

To solve this problem, we can use a counter, since that contains the numbers and counts of each number.

We dfs as normal as we would in combination sum, but instead of iterating through all the candidates, we iterate through the counter and we check to make sure the counter's value is greater than 1 indicating the number still exists in the counter.

We then add that number to our list and dfs through the list, and pop and readd the item to the counter to reverse the backtracking.

def test(): View Source

51def test():
52    assert 2 + 2 == 4