leetcode Binary Tree Depth-First Search

leetcode 39题

Posted by franki on December 3, 2020

leetcode 39题 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

题解：

思路

利用搜索回溯求解

  • 定义递归函数dfs(target, combine, idx)表示在candidates数组在第idx位，还剩下target要组合，已经组合的列表combine
  • 递归的终止条件是target <= 0 或者 candidates 数组全部被用完。
  • 在当前函数中，我们可以选择跳过不用第idx个数，即是dfs(target, combine, idx+1)
  • 也可以选择使用第idx个数，即是dfs(target-candidates[idx], […combine, candidates[idx]], idx)
  • 注意这个数字是可以被无限选取的，因此下标仍为idx
  • 每次搜索都可以延伸出两个分叉，直到递归的终止条件，这样我们就能不重复且不遗漏地找出所有的可行解

如下图分析：

combineSum

代码

function combinationSum(candidates, target) {
    const ans = [];

    const dfs = (target, combine, idx) => {
        if (idx === candidates.length) {
            return;
        }
        if (target === 0) {
            ans.push(combine);
            return;
        }
        dfs(target, combine, idx+1);
        if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
        }
    };

    dfs(target, [], 0);
    return ans;
}

复杂度分析

  • 时间复杂度: O(S)
  • 空间复杂度: O(H)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS