FilesExpand file tree

master

/

combination_sum_iv.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

102 lines (79 loc) · 2.75 KB

master

/

combination_sum_iv.py

Copy path

Top

File metadata and controls

• Code
• Blame

102 lines (79 loc) · 2.75 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

"""

Question:

You are given an array of distinct integers and you have to tell how many

different ways of selecting the elements from the array are there such that

the sum of chosen elements is equal to the target number tar.

Example

Input:

N = 3

target = 5

array = [1, 2, 5]

Output:

9

Approach:

The basic idea is to go over recursively to find the way such that the sum

of chosen elements is “tar”. For every element, we have two choices

1. Include the element in our set of chosen elements.

2. Don’t include the element in our set of chosen elements.

"""

def combination_sum_iv(n: int, array: list[int], target: int) -> int:

"""

Function checks the all possible combinations, and returns the count

of possible combination in exponential Time Complexity.

>>> combination_sum_iv(3, [1,2,5], 5)

9

"""

def count_of_possible_combinations(target: int) -> int:

if target < 0:

return 0

if target == 0:

return 1

return sum(count_of_possible_combinations(target - item) for item in array)

return count_of_possible_combinations(target)

def combination_sum_iv_dp_array(n: int, array: list[int], target: int) -> int:

"""

Function checks the all possible combinations, and returns the count

of possible combination in O(N^2) Time Complexity as we are using Dynamic

programming array here.

>>> combination_sum_iv_dp_array(3, [1,2,5], 5)

9

"""

def count_of_possible_combinations_with_dp_array(

target: int, dp_array: list[int]

) -> int:

if target < 0:

return 0

if target == 0:

return 1

if dp_array[target] != -1:

return dp_array[target]

answer = sum(

count_of_possible_combinations_with_dp_array(target - item, dp_array)

for item in array

)

dp_array[target] = answer

return answer

dp_array = [-1] * (target + 1)

return count_of_possible_combinations_with_dp_array(target, dp_array)

def combination_sum_iv_bottom_up(n: int, array: list[int], target: int) -> int:

"""

Function checks the all possible combinations with using bottom up approach,

and returns the count of possible combination in O(N^2) Time Complexity

as we are using Dynamic programming array here.

>>> combination_sum_iv_bottom_up(3, [1,2,5], 5)

9

"""

dp_array = [0] * (target + 1)

dp_array[0] = 1

for i in range(1, target + 1):

for j in range(n):

if i - array[j] >= 0:

dp_array[i] += dp_array[i - array[j]]

return dp_array[target]

if __name__ == "__main__":

import doctest

doctest.testmod()

n = 3

target = 5

array = [1, 2, 5]

print(combination_sum_iv(n, array, target))