77. Combinations

Backtracking

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(resultList, path, 1, n, k);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int start, int n, int k) {
        if (path.size() == k) {
            resultList.add(new ArrayList<>(path));
        }

        for (int i = start; i <= n; i++) {
            path.add(i);
            dfs(resultList, path, i + 1, n, k);
            path.removeLast();
        }
    }
}

Backtracking

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(resultList, path, 1, n, k);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int start, int n, int k) {
        if (path.size() == k) {
            resultList.add(new ArrayList<>(path));
            return; // 注意，当下方采用了剪枝的逻辑后，此处需要显式 return, 否则当 path.size() == k 时，判断逻辑将变为 i <= n + 1, 导致进入循环继续添加元素，最后栈溢出
        }

        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            dfs(resultList, path, i + 1, n, k);
            path.removeLast();
        }
    }
}

Backtracking

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(resultList, path, 1, n, k);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int value, int n, int k) {
        if (value == n + 1) {
            if (path.size() == k) {
                resultList.add(new ArrayList<>(path));
            }
            return;
        }

        // choose
        path.add(value);
        dfs(resultList, path, value + 1, n, k);
        path.removeLast();
        
        // not choose
        dfs(resultList, path, value + 1, n, k);
    }
}

Backtracking

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(resultList, path, 1, n, k);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int value, int n, int k) {
        if (path.size() == k) {
            resultList.add(new ArrayList<>(path));
            return;
        }

        if (value > n - (k - path.size()) + 1) {
            return;
        }

        // choose
        path.add(value);
        dfs(resultList, path, value + 1, n, k);
        path.removeLast();

        // not choose
        dfs(resultList, path, value + 1, n, k);
    }
}

Reference

77. Combinations