StarWalker

Where my heart will take me

0%

Leetcode077-combinations

Posted on Edited on In Views: Valine:
Solution Report of LeetCode Acceptted

Description

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

Example

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void backtracking(List<List<Integer>> res, List<Integer> tmp, int k, int n, int start){
        if (tmp.size() == k){
            res.add(new ArrayList<Integer>(tmp));
            return;
        }
        for (int i = start;i <= n - (k-tmp.size()) + 1; i++){ //notice i<=n-(k-tmp.size())+1 speed up from 26ms downto 2ms
            tmp.add(i);
            backtracking(res, tmp, k, n, i+1);
            tmp.remove(tmp.size()-1);
        }
    }
    
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k>n) return res;
        backtracking(res, new ArrayList<Integer>(), k, n, 1);
        return res;
    }
}