代码随想录算法训练营第二十一天-理论基础、77组合

前言
状态：理论基础总结在 [[面试-数据结构和算法]] 中。
更新

1	24-05-10 初始记录

初步题解

77 组合

题目链接：(https://leetcode.cn/problems/combinations/)

public List<List<Integer>> combine(int n, int k) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> list = new ArrayList<>();  
    combineDFS(1, n, k, list, result);  
    return result;  
}  
  
/**  
 * * @param start 当前开始节点  
 * @param n n  
 * @param k k  
 * @param list 每个list  
 * @param result 最后的结果  
 */  
private void combineDFS(int start, int n, int k, List<Integer> list, List<List<Integer>> result) {  
    if (list.size() == k) {  
        List<Integer> resultOne = new ArrayList<>(k);  
        resultOne.addAll(list);  
        result.add(resultOne);  
        return;  
    }  
  
    for (int j = start; j <= n; j++) {  
        list.add(j);  
        combineDFS(j + 1, n, k, list, result);  
        list.remove(list.size() - 1);  
    }  
}

看解析

77 组合

题目链接/文章讲解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

视频讲解：https://www.bilibili.com/video/BV1ti4y1L7cv

剪枝操作：https://www.bilibili.com/video/BV1wi4y157er

public List<List<Integer>> combine(int n, int k) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> list = new ArrayList<>();  
    combineDFS(1, n, k, list, result);  
    return result;  
}  
  
/**  
 * * @param start 当前开始节点  
 * @param n n  
 * @param k k  
 * @param list 每个list  
 * @param result 最后的结果  
 */  
private void combineDFS(int start, int n, int k, List<Integer> list, List<List<Integer>> result) {  
    if (list.size() == k) {  
        List<Integer> resultOne = new ArrayList<>(k);  
        resultOne.addAll(list);  
        result.add(resultOne);  
        return;  
    }  

	// 附带剪枝操作
    for (int j = start; j <= (n - (k - list.size())) + 1; j++) {  
        list.add(j);  
        combineDFS(j + 1, n, k, list, result);  
        list.remove(list.size() - 1);  
    }  
}