FilesExpand file tree

 master

/

Combinations.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

42 lines (41 loc) · 1.1 KB

 master

/

Combinations.java

Top

File metadata and controls

• Code
• Blame

42 lines (41 loc) · 1.1 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

/*

Author: King, wangjingui@outlook.com

Date: Dec 20, 2014

Problem: Combinations

Difficulty: Easy

Source: https://oj.leetcode.com/problems/combinations/

Notes:

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

Solution: DFS.

*/

public class Solution {

public List<List<Integer>> combine(int n, int k) {

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

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

combineRe(n, k, 1, path, res);

return res;

}

void combineRe(int n, int k, int start, ArrayList<Integer> path, List<List<Integer>> res){

int m = path.size();

if (m == k) {

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

res.add(p);

return;

}

for (int i = start; i <= n-(k-m)+1; ++i) {

path.add(i);

combineRe(n,k,i+1, path, res);

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

}

}

}