77. Combinations

Combinations

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

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        combine(result, n, 1, k, new ArrayList<>());
        return result;

    }

    public void combine(List<List<Integer>> result, int n, int start, int k, List<Integer> current) {
        if (k == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for(int i = start; i <= n; i ++) {
            current.add(i);
            combine(result, n, i + 1, k - 1, current);
            current.remove(current.size()-1);
        }
    }
}