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], ]

combinations.java

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> solution = new ArrayList<>();
        dfs(n, k, 1, solution, new ArrayList<Integer>());
        return solution;
    }
    
    private void dfs(int n, int k, int start, List<List<Integer>> l, List<Integer> path) {
        if(k == 0) {
            l.add(path);
            return;
        }
        
        for(int i = start ; i <= n; i++) {
            List<Integer> nPath = new ArrayList<>(path);
            nPath.add(i);
            dfs(n, k - 1, i + 1, l ,nPath);
        }
    }
}