FilesExpand file tree

 master

/

CombinationSum39.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (55 loc) · 1.7 KB

 master

/

CombinationSum39.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (55 loc) · 1.7 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

/**

* Given a set of candidate numbers (candidates) (without duplicates) and a

* target number (target), find all unique combinations in candidates where

* the candidate numbers sums to target.

*

* The same repeated number may be chosen from candidates unlimited number of times.

*

* Note:

* All numbers (including target) will be positive integers.

* The solution set must not contain duplicate combinations.

*

* Example 1:

* Input: candidates = [2,3,6,7], target = 7,

* A solution set is:

* [

* [7],

* [2,2,3]

* ]

*

* Example 2:

* Input: candidates = [2,3,5], target = 8,

* A solution set is:

* [

* [2,2,2,2],

* [2,3,3],

* [3,5]

* ]

*/

public class CombinationSum39 {

public List<List<Integer>> combinationSum(int[] candidates, int target) {

List<List<Integer>> res = new ArrayList<>();

helper(candidates, target, 0, new ArrayList<Integer>(), res);

return res;

}

private void helper(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {

if (target < 0) return;

if (target == 0) {

List<Integer> newPath = new ArrayList<Integer>();

for (Integer i: path) newPath.add(i);

res.add(newPath);

}

for (int i = start; i<candidates.length; i++) {

int c = candidates[i];

int count = target / c;

if (count >= 1) {

for (int j=1; j<= count; j++) {path.add(c);}

while (count >= 1) {

helper(candidates, target - c * count, i+1, path, res);

path.remove(path.size() - 1);

count--;

}

}

}

}

}