3月7日代码随想录组合及优化

时间：2024-03-07 20:14:18

77.组合

77. 组合 - 力扣（LeetCode）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

思路

若是使用for循环嵌套组合1到n中的数，若k取大一点就会有非常多的嵌套for要写，明显是不合适的，所以这里引入了回溯的思想，直观的想法是画出递归树，这里引用了力扣大佬画的图

 这里我们需要使用一个表示路径的栈path去记录已选择的数。

class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res=new ArrayList<>();//答案
            if(k<=0||n<k){
                return res;
            }
            Deque<Integer> path=new ArrayDeque<>();
            dfs(n,k,1,path,res);//题目要求从1开始
            return res;
        }
        private void dfs(int n,int k,int begin,Deque<Integer> path,List<List<Integer>> res){
            if(path.size()==k){//如果path长度已经=要寻找的数个数，说明找到一组答案
                res.add(new ArrayList<>(path));
                return;
            }

            for(int i=begin;i<=n-(k-path.size())+1;i++){//此处是一个优化思想，如果n=7，k=4，那么从5开始搜索已经没有意义了，所以搜索起点有上界。
                path.addLast(i);//将当前节点记录进path
                dfs(n,k,i+1,path,res);//将path传入下一次递归从i+1开始寻找
                path.removeLast();//将该节点删除，代表了回溯的操作。
            }
        }
    }

思路2.按照每一个数选与不选递归。

public class Solution {

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

        // 为了防止底层动态数组扩容，初始化的时候传入最大长度
        Deque<Integer> path = new ArrayDeque<>(k);
        dfs(1, n, k, path, res);
        return res;
    }

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

        if (begin > n - k + 1) {
            return;
        }
        // 不选当前考虑的数 begin，直接递归到下一层
        dfs(begin + 1, n, k, path, res);

        // 不选当前考虑的数 begin，递归到下一层的时候 k - 1，这里 k 表示还需要选多少个数
        path.addLast(begin);
        dfs(begin + 1, n, k - 1, path, res);
        // 深度优先遍历有回头的过程，因此需要撤销选择
        path.removeLast();
    }
}

总结

回溯法第一题卡了好几天，需要加强复习。

相关文章