FilesExpand file tree

 master

/

combination_sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (51 loc) · 1.42 KB

 master

/

combination_sum.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (51 loc) · 1.42 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

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]

target = 4

The possible combination ways are:

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(1, 3)

(2, 1, 1)

(2, 2)

(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:

What if negative numbers are allowed in the given array?

How does it change the problem?

What limitation we need to add to the question to allow negative numbers?

private int[] dp;

public int combinationSum4(int[] nums, int target) {

dp = new int[target + 1];

Arrays.fill(dp, -1);

dp[0] = 1;

return helper(nums, target);

}

private int helper(int[] nums, int target) {

if (dp[target] != -1) {

return dp[target];

}

int res = 0;

for (int i = 0; i < nums.length; i++) {

if (target >= nums[i]) {

res += helper(nums, target - nums[i]);

}

}

dp[target] = res;

return res;

}

EDIT: The above solution is top-down. How about a bottom-up one?

public int combinationSum4(int[] nums, int target) {

int[] comb = new int[target + 1];

comb[0] = 1;

for (int i = 1; i < comb.length; i++) {

for (int j = 0; j < nums.length; j++) {

if (i - nums[j] >= 0) {

comb[i] += comb[i - nums[j]];

}

}

}

return comb[target];

}