Leetcode/77. Combinations.java at main · krishna-o73/Leetcode · GitHub

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
//https://leetcode.com/problems/combinations/description/
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    void solve1(int num, int tot, int k, List<Integer> ans) {
        if (num == tot + 1) {
            if (ans.size() == k) {
                res.add(new ArrayList<>(ans));
            }
            return;
        }

        ans.add(num);
        solve1(num + 1, tot, k, ans);
        ans.remove(ans.size() - 1);
        solve1(num + 1, tot, k, ans);
    }

    void solve2(int num, int tot, int k, List<Integer> ans) {
        if (ans.size() == k) {
            res.add(new ArrayList<>(ans));
            return;
        }
        for (int i = num; i <= tot; i++) {
            ans.add(i);
            solve2(i + 1, tot, k, ans);
            ans.remove(ans.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<Integer> ans = new ArrayList<>();
        solve2(1, n, k, ans);
        return res;
    }
}