加载中...
jk式万能回溯法
发表于:2022-02-08 | 分类: Leetcode刷题笔记
字数统计: 293 | 阅读时长: 1分钟 | 阅读量:

步骤:

  1. 画出解空间树型图
  2. 根据经验写出dfs需要的参数
  3. 写上结束条件
  4. 根据树型图写出for循环,并与图中每一层比较是否对应
  5. 接下来套回溯模版即可
  6. 若返回值需要存入数据结构且会被回溯清空,需要另外备份一份才能存入

使用案例1:leetcode77 组合


配套使用方法:

  1. 假设n=4,k=3,则画出树型图如下:

  1. 思考dfs需要的参数:n,k,当前到第几个数了index,当前的临时tempList
  2. 结束条件:index到n,说明已经找到一个解了
  3. for循环:若index=0,则从1开始,否则从上一个存入的数+1开始,一直到k结束

    代码答案:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public List<List<Integer>> ans = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
    dfs(k,0,new LinkedList<Integer>(),n);
    return ans;
    }
    public void dfs(int numOfList,int curindex,List<Integer> temp,int maxNum){
    if(curindex == numOfList){
    ans.add(new LinkedList<Integer>(temp));
    return;
    }
    for(int i = (temp.isEmpty() ? 1 :temp.get(curindex-1)+1);i <= maxNum;i++){
    temp.add(i);
    dfs(numOfList,curindex+1,temp,maxNum);
    temp.remove(curindex);
    }
    }



上一篇:
Spark逻辑处理流程
下一篇:
概率论基本知识
本文目录
本文目录