侧边栏壁纸
  • 累计撰写 43 篇文章
  • 累计创建 0 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

DFS中的递归问题

汉诺塔

分支污染问题

理解 本贴 分支污染问题递归分支污染对结果的影响

recursion_and_dfs_02.png

  • Java 代码

    // 体会分支污染问题
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<Integer> cur = new ArrayList<>();
            dfs(cur, candidates, target);
            return res;
        }
    
        private void dfs(List<Integer> cur, int[] a, int target) {
            if (target == 0) {
                res.add(new ArrayList<>(cur));
                return;
            }
    
            for (int i = 0; i < a.length; i++) {
                if (target < a[i]) continue;
                cur.add(a[i]);
                dfs(cur, a, target - a[i]);
            }
        }
    
        private List<List<Integer>> res = new ArrayList<>();
    }
    
    // 解决分支污染问题
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<Integer> cur = new ArrayList<>();
            dfs(cur, candidates, target);
            return res;
        }
    
        private void dfs(List<Integer> cur, int[] a, int target) {
            if (target == 0) {
                res.add(new ArrayList<>(cur));
                return;
            }
    
            for (int i = 0; i < a.length; i++) {
                if (target < a[i]) continue;
                List<Integer> list = new ArrayList<>(cur);
                list.add(a[i]);
                dfs(list, a, target - a[i]);
            }
        }
    
        private List<List<Integer>> res = new ArrayList<>();
    }
    
    // 也可以这样写
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<Integer> cur = new ArrayList<>();
            dfs(cur, candidates, target);
            return res;
        }
    
        private void dfs(List<Integer> cur, int[] a, int target) {
            if (target == 0) {
                res.add(new ArrayList<>(cur));
                return;
            }
    
            for (int i = 0; i < a.length; i++) {
                if (target < a[i]) continue;
                cur.add(a[i]);
                dfs(cur, a, target - a[i]);
                cur.remove(cur.size() - 1);	// 利用回溯解决分支污染问题
            }
        }
    
        private List<List<Integer>> res = new ArrayList<>();
    }
    

体会

关键还是画出递归树,有递归树就很好写了。

0

评论区