LeetCode 77. 组合

力扣

public class Combine {

    public List> resultList = new ArrayList<>();
    public LinkedList pathList = new LinkedList<>();

    public List> combine(int n, int k) {
        if (n == 0) {
            return new ArrayList<>();
        }

        dfsForCombine(n, k, 1);
        return resultList;
    }

    public void dfsForCombine(int n, int k, int start) {
        if (pathList.size() == k) {
            resultList.add(new ArrayList<>(pathList));
            return;
        }

        // 剪枝：元素个数
        for (int i = start; i <= n - (k - pathList.size()) + 1; i++) {
            pathList.add(i);
            dfsForCombine(n, k, i + 1);
            pathList.removeLast();
        }
    }
}

剪枝：

pathList.size() 为已选择元素个数，k 是总的元素总数，(k - pathList.size()) 为待选择的元素总数，所以 for 遍历的最多从 index = n - (k - pathList.size()) + 1 开始。