FilesExpand file tree

 master

/

CombinationSum.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

43 lines (41 loc) · 1.6 KB

 master

/

CombinationSum.java

Top

File metadata and controls

• Code
• Blame

43 lines (41 loc) · 1.6 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

/*

Author: Annie Kim, anniekim.pku@gmail.com

Date: May 25, 2013

Problem: Combination Sum

Difficulty: Easy

Source: http://leetcode.com/onlinejudge#question_39

Notes:

Given a set of candidate numbers (C) and a target number (T), find all unique

combinations in C where the candidate numbers sums to T.

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

Note:

All numbers (including target) will be positive integers.

Elements in a combination (a1, a2, .. , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak).

The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,

A solution set is:

[7]

[2, 2, 3]

Solution: Sort & Recursion.

*/

public class Solution {

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

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

Arrays.sort(candidates);

ArrayList<Integer> path = new ArrayList<Integer>();

combinationSumRe(candidates, target, 0, path, res);

return res;

}

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

if (target == 0) {

ArrayList<Integer> p = new ArrayList<Integer>(path);

res.add(p);

return;

}

for (int i = start; i < candidates.length && target >= candidates[i]; ++i) {

path.add(candidates[i]);

combinationSumRe(candidates, target-candidates[i], i, path, res);

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

}

}

}