Skip to content

Latest commit

 

History

History
634 lines (555 loc) · 28.8 KB

算法相关总结.md

File metadata and controls

634 lines (555 loc) · 28.8 KB

总结

  1. 常见方法：Backtracking, 贪心，DP，二分搜索，Two Pointer（搜索，链表）

  2. 需要熟练掌握，能够快速手写的算法：排序（快排（递归，非递归），冒泡，...），二叉树遍历（前序，中序，后续 （递归和非递归）），链表（翻转，...）

  3. 二分搜索注意的地方：

    1. mid  = lo + (hi - lo)/2 ，如果写成 mid = (lo + hi)/2 的话， lo + hi 可能溢出
    2. 结束的条件是 i<j还是 i<=j

  4. 排序（部分排序）数组常用的方法：二分搜索，双指针

  5. 递归和迭代（栈）可以相互转换：快排，二叉树遍历

  6. 位操作：https://leetcode.com/problems/missing-number/solution/

  7. 一些小技巧：移位代替乘除法、 v & 0x01  判断奇偶数

  8. 树的问题一般可以用递归解决（分解为子问题：左子树+右子树）

排序及其应用

快速排序

https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F 相关题型：最小的 k 个数

// todo

归并排序

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F 相关题型：

  1. 数组中的逆序对（https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/）
  2. 合并 K 个升序链表（https://leetcode-cn.com/problems/merge-k-sorted-lists/）
class Solution { 
	private void msort(int[] tmp, int[] nums, int start, int end) {
        //System.out.println("FUCK\tstart: " + start + "\tend: " + end);
        if (start >= end) return;

        int mid = start + (end - start)/2;
        msort(tmp, nums, start, mid);
        msort(tmp, nums, mid + 1, end);
        
        // merge
        int k = start;
        int i = start, j = mid + 1;
        while (i <= mid && j <= end) tmp[k++] = nums[i] <= nums[j]?nums[i++]:nums[j++];
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= end) tmp[k++] = nums[j++];

        // copy to origin arr
        System.arraycopy(tmp, start, nums, start, end - start + 1);
        System.out.println("start: " + start + "\tend: " + end + "\tnums: " + Arrays.toString(nums));
    }

    // 非递归
    private void msort2(int[] nums) {
        int[] tmp = new int[nums.length];

        for (int step = 1; step < nums.length; step*=2) {
            for (int i = 0; i < nums.length; i+=step*2) {
                int low = i, mid = Math.min(low + step, nums.length), high = Math.min(low + step*2, nums.length);
                int k = low;
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                System.out.println("low: " + low + "\tmid: " + mid + "\thigh: " + high);
                while (start1 < end1 && start2 < end2) tmp[k++] = nums[start1] <= nums[start2]?nums[start1++]:nums[start2++];
                while (start1 < end1) tmp[k++] = nums[start1++];
                while (start2 < end2) tmp[k++] = nums[start2++];
                System.arraycopy(tmp, low, nums, low, high - low);
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}

链表

反转链表（[LeetCode] 206. Reverse Linked List [Easy]）

https://leetcode.com/problems/reverse-linked-list/

public class LeetCode206 {
    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode curNode = head;
        ListNode preNode = null;

        while (curNode != null) {
            ListNode tmp = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = tmp;
        }

        return preNode;
    }
}

递归解法： //todo

Merge链表（[LeetCode] 21. Merge Two Sorted Lists [Easy]）

https://leetcode.com/problems/merge-two-sorted-lists/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class LeetCode21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        ListNode p1 = l1, p2 = l2;
        while (p1 != null && p2 != null) {
            if(p1.val < p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        cur.next = p1 == null?p2:p1;

        return dummy.next;
    }
}

递归解法 //todo

扩展：合并 K 个升序链表（https://leetcode-cn.com/problems/merge-k-sorted-lists/）

二叉树遍历

ref: https://www.yuque.com/littleneko/yxpqg3/tglck4

前序（[LeetCode] 144. Binary Tree Preorder Traversal [Medium]）

中序（[LeetCode] 94. Binary Tree Inorder Traversal [Medium]）

后序（[LeetCode] 145. Binary Tree Postorder Traversal [Hard]）

层序

回溯法（DFS/Backtracking）

回溯法实际上是一种带有剪枝的 DFS ，遍历过程中把不符合条件的分支剪掉，然后返回上一层继续遍历。使用回溯法的分析方法是先画出完整的 DFS 树，再分析怎么剪枝。

LeetCodeCNOffer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制： 1 <= s 的长度 <= 8

解题思路： 排列方案数量： 对于一个长度为 n 的字符串（假设字符互不重复），其排列共有 n×(n−1)×(n−2)…×2×1 种方案。

排列方案的生成方法： 根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第 1 位字符（ n 种情况）、再固定第 2 位字符（n−1 种情况）、... 、最后固定第 n 位字符（ 1 种情况）。    image.png 重复方案与剪枝： 当字符串存在重复字符时，排列方案中也存在重复方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。    image.png

递归解析：

  1. 终止条件： 当 x = len(c) - 1 时，代表所有位已固定（最后一位只有 11 种情况），则将当前组合 c 转化为字符串并加入 res，并返回；
  2. 递推参数： 当前固定位 x ；
  3. 递推工作： 初始化一个 Set ，用于排除重复的字符；将第 x 位字符与 i∈[x,len(c)] 字符分别交换，并进入下层递归；
    1. 剪枝： 若 c[i] 在 Set 中，代表其是重复字符，因此“剪枝”；
    2. 将 c[i] 加入 Set ，以便之后遇到重复字符时剪枝；
    3. 固定字符： 将字符 c[i] 和 c[x] 交换，即固定 c[i] 为当前位字符；
    4. 开启下层递归： 调用 dfs(x+1) ，即开始固定第 x+1 个字符；
    5. 还原交换： 将字符 c[i] 和 c[x] 交换（还原之前的交换）；
public class LeetCodeCNOffer38 {
    public String[] permutation(String s) {
        List<String> res = new ArrayList<>();
        backtracking(res, s.toCharArray(), 0);
        return res.toArray(new String[0]);
    }

    /**
     * @param res
     * @param s
     * @param idx 当前固定的位置，搜索树第idx层
     */
    private void backtracking(List<String> res, char[] s, int idx) {
        if (idx == s.length - 1) {
            res.add(String.valueOf(s));
            return;
        }

        HashSet<Character> set = new HashSet<>();
        // idx 表示当前步骤是在固定第 idx 位的字符
        // 固定第idx位字符有（s.length - idx）种情况可选，比如对于输入[a, b, c]，固定第1位字符，只有2个字符可选
        // * 第0位选择了 "a"，第1位只能选择 "b", "c"
        // * 第0位选择了 "b"，第1位只能选择 "a", "c"
        // * 第0位选择了 "c"，第1位只能选择 "a", "b"
        //
        // 实际上因为这里做了swap，能选择的字符只能在原数组 [idx, s.length) 位置上
        // 即这里的idx实际上也表示了需要从数组 idx 位置选择字符放入结果集中
        //
        // 循环中的 i 表示第 idx 位选择的字符为 c[i]
        // 比如 idx = 0, i = 0（即首次循环时）表示第 0 位 选择 "a"
        //
        // 从原数组 idx 位置开始选择字符放入结果集中
        for (int i = idx; i < s.length; i++) {
            if (set.contains(s[i])) continue;
            set.add(s[i]);
            swap(s, i, idx);
            System.out.println("[I] idx=" + idx + ", i=" + i + ", ci=" + s[idx] + ", s=" + Arrays.toString(s));
            // 接着固定第 idx + 1 位字符
            backtracking(res, s, idx + 1);
            swap(s, idx, i);
        }
    }

    private void swap(char[] s, int i, int j) {
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }

    public static void main(String[] args) {
        String[] res = new LeetCodeCNOffer38().permutation("abc");
        System.out.println(Arrays.toString(res));
    }
}

REF: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/

我们打印出每次进入DFS前的 idx 和 i ，得到如下结果：

// 注意：
// 这里并不会打印出最后一位选择的情况，因为最后一位只有一个选择了
// 代码中可以看到 x == c.length - 1 就直接把c加到结果集中然后返回了，并不会进下面的选择逻辑

[I] idx=0, i=0, ci=a, s=[a, b, c] // 第 0 位选择 "a"
[I] idx=1, i=1, ci=b, s=[a, b, c] // 第 1 位选择 "b"
[I] idx=1, i=2, ci=c, s=[a, c, b] // 第 1 位选择 "c"

[I] idx=0, i=1, ci=b, s=[b, a, c] // 第 0 位选择 "b"
[I] idx=1, i=1, ci=a, s=[b, a, c] // 第 1 位选择 "a"
[I] idx=1, i=2, ci=c, s=[b, c, a] // 第 1 位选择 "c"

[I] idx=0, i=2, ci=c, s=[c, b, a] // 第 0 位选择 "c"
[I] idx=1, i=1, ci=b, s=[c, b, a] // 第 1 位选择 "b"
[I] idx=1, i=2, ci=a, s=[c, a, b] // 第 1 位选择 "a"

ret: [abc, acb, bac, bca, cba, cab]

一个更容易理解的解法。但没上面这个效率高:

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ret;
        string cur_ret;
        unordered_set<int> filter;
        backtracking(ret, cur_ret, s, filter);
        return ret;
    }

    // filter 用来保证不同层不能选同一个元素, 但是可以选相同的值, 因此要用 index
    void backtracking(std::vector<string>& ret, string& cur_ret, const string& s, unordered_set<int>& filter) {
        if (cur_ret.length() == s.length()) {
            ret.push_back(cur_ret);
            return;
        }

        // 保证同一层不能选重复的
        std::unordered_set<char> sel;
        for (int i = 0; i < s.length(); i++) {
            if (!filter.empty() && filter.find(i) != filter.end()) continue;
            if (!sel.empty() && sel.find(s[i]) != sel.end()) continue;
            sel.insert(s[i]);

            cur_ret.append(1, s[i]);
            filter.insert(i);
            backtracking(ret, cur_ret, s, filter);
            filter.erase(i);
            cur_ret = cur_ret.substr(0, cur_ret.length() - 1);
        }
    }
};

LeetCode 39&40. Combination Sum

https://leetcode.com/problems/combination-sum/ Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

DFS 方案生成： 与 LeetCodeCNOffer 38 不同的地方是：

  1. LeetCodeCNOffer 38 的排列组合数在没有剪枝的情况下是有限的，因为确定了排列的最大长度，而该题的长度是可以无限的。
  2. LeetCodeCNOffer 38 每次选择第 x 位置的字符可选择的情况有 N - x 种，原因是每个字符只能使用 1 次；而该题 x 位置数字可选择的数量都是 N 种，因为每个数字可以使用无限次（实际不需要 n，后面会分析怎么剪枝）

因此 DFS 方案为：先固定第 1 位字符（ n 种情况）、再固定第 2 位字符（n 种情况）、... ... （无限多）

对于 candidates = [2,3,5], target = 8，我们按 DFS 遍历得到所有组合的结果是这样（省略无穷多行）：    image.png ([2,3,5]不加任何限制情况下的DFS)

图中只画出了部分路径，如果不加限制，会一只递归下去；加上限制，有些路径就可以剪掉：

  1. 如果 target 减去一个数得到负数，那么减去一个更大的树依然是负数，同样搜索不到结果。基于这个想法，我们可以对输入数组进行排序，添加相关逻辑达到进一步剪枝的目的。图中的路径 (2, 3, 5) 和 (2, 5, 5)，遍历到这里后后面就可以不用再遍历了，因为 sum 已经大于 8 了。
  2. (3, 2, 3) 这样的路径也可以不用遍历，因为和 (2, 3, 3) 重复了，因此我们这里可以每一轮选择不是从第 0 个元素开始，而是从第 n 个。
public class LeetCode39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(ret, new ArrayList<Integer>(), candidates, target, 0);
        return ret;
    }

    /**
     * @param ret
     * @param cur
     * @param candidates
     * @param target
     * @param start      当前应该从第 start 位的数字开始选择
     */
    private void backtracking(List<List<Integer>> ret, List<Integer> cur, int[] candidates, int target, int start) {
        if (target < 0) return;
        if (target == 0) {
            ret.add(new ArrayList<>(cur));
            return;
        }

        // 这里并没有直接记录当前是在固定第几位的数字，其实这个idx隐藏在cur.size()中了
        // start 表示本次应该从start位置开始选择数字，我们要求第idx位置选择的数字要大于等于idx-1位的数字
        // 这里每个位置有 N - start 种情况可选，比如对于[2, 3, 5]的输入，上一个位置选择了3（start = 1），那么当前位置就只能选择 3, 5 (idx=1, 2) 了
        //
        // 从输入数组start位置开始选择数字放入结果集中，i 表示本次选择第 i 位置的数字
        for (int i = start; i < candidates.length; i++) {
            // 剪枝，后面不用再遍历下去了
            if (target - candidates[i] < 0) break;
            // 把第 i 位的数字加到当前结果集中
            cur.add(candidates[i]);
            System.out.println("[I] idx=" + (cur.size() - 1)  + ", i=" + i + ", ni=" + candidates[i] + ", startIdx=" + start + ", startNum=" + candidates[start] + ", cur=" + cur);
            // 选择下一位置的数字，起始位置(start)仍然是 i
            backtracking(ret, cur, candidates, target - candidates[i], i);
            cur.remove(cur.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> ret = new LeetCode39().combinationSum(new int[]{2, 3, 5}, 8);
        System.out.println(ret);
    }
}

对比 LeetCodeCNOffer 38 中的 idx 变量，实际上 idx 不仅表示当前在处理的位置，还充当了这里的 start 变量的角色

我们打印出每次进入 DFS 前的 start 和 i ，得到如下结果：

[I] idx=0, i=0, ni=2, startIdx=0, startNum=2, cur=[2] // 第 0 位选择 2
[I] idx=1, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2] // 第 1 位选择 2
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2, 2] // 第 2 位选择 2
[I] idx=3, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2, 2, 2] // 第 3 位选择 2
[I] idx=3, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 2, 2, 3] // 第 3 位选择 3，sum超过了8，剪枝（返回上层）
[I] idx=3, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 2, 2, 5] // 第 3 位选择 5，sum超过了8，剪枝（返回上层）
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 2, 3] // 第 2 位选择 3
[I] idx=3, i=1, ni=3, startIdx=1, startNum=3, cur=[2, 2, 3, 3] // 第 3 位选择 3，sum超过了8，剪枝（返回上层）
[I] idx=3, i=2, ni=5, startIdx=1, startNum=3, cur=[2, 2, 3, 5] // 第 3 位选择 5，sum超过了8，剪枝（返回上层）
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 2, 5]  // 第 2 位选择 5，sum超过了8，剪枝（返回上层）
[I] idx=1, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 3]  // 第 1 位选择 3
[I] idx=2, i=1, ni=3, startIdx=1, startNum=3, cur=[2, 3, 3]
[I] idx=2, i=2, ni=5, startIdx=1, startNum=3, cur=[2, 3, 5]
[I] idx=1, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 5]
[I] idx=2, i=2, ni=5, startIdx=2, startNum=5, cur=[2, 5, 5]

[I] idx=0, i=1, ni=3, startIdx=0, startNum=2, cur=[3] // 第 0 位选择 3
[I] idx=1, i=1, ni=3, startIdx=1, startNum=3, cur=[3, 3] // 第 1 位选择 3，这里不能选择 2 了
[I] idx=2, i=1, ni=3, startIdx=1, startNum=3, cur=[3, 3, 3]
[I] idx=2, i=2, ni=5, startIdx=1, startNum=3, cur=[3, 3, 5]
[I] idx=1, i=2, ni=5, startIdx=1, startNum=3, cur=[3, 5] // 第 1 位选择 5

[I] idx=0, i=2, ni=5, startIdx=0, startNum=2, cur=[5]
[I] idx=1, i=2, ni=5, startIdx=2, startNum=5, cur=[5, 5]

ret: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

上面的情况是限定了每次选择的时候第 idx 位的数字需要大于等于第 idx - 1 位的数字，可以看到在第 0 位选择了 3 的时候，第 1 位只有 [3, 5] 两种选择。

如果我们不做这个限定，即每个位置都可以放 N 种情况的数字：

[I] idx=0, i=0, ni=2, startIdx=0, startNum=2, cur=[2]
[I] idx=1, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2]
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2, 2]
[I] idx=3, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2, 2, 2]
[I] idx=3, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 2, 2, 3]
[I] idx=3, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 2, 2, 5]
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 2, 3]
[I] idx=3, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 2, 3, 2]
[I] idx=3, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 2, 3, 3]
[I] idx=3, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 2, 3, 5]
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 2, 5]
[I] idx=1, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 3]
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 3, 2]
[I] idx=3, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 3, 2, 2]
[I] idx=3, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 3, 2, 3]
[I] idx=3, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 3, 2, 5]
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 3, 3]
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 3, 5]
[I] idx=1, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 5]
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[2, 5, 2]
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[2, 5, 3]
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[2, 5, 5]

[I] idx=0, i=1, ni=3, startIdx=0, startNum=2, cur=[3] // 第 0 位选择 3
[I] idx=1, i=0, ni=2, startIdx=0, startNum=2, cur=[3, 2] // 第 1 位选择 2，这里没有做限定
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[3, 2, 2]
[I] idx=3, i=0, ni=2, startIdx=0, startNum=2, cur=[3, 2, 2, 2]
[I] idx=3, i=1, ni=3, startIdx=0, startNum=2, cur=[3, 2, 2, 3]
[I] idx=3, i=2, ni=5, startIdx=0, startNum=2, cur=[3, 2, 2, 5]
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[3, 2, 3]
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[3, 2, 5]
[I] idx=1, i=1, ni=3, startIdx=0, startNum=2, cur=[3, 3] // 第 1 位选择 3
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[3, 3, 2]
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[3, 3, 3]
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[3, 3, 5]
[I] idx=1, i=2, ni=5, startIdx=0, startNum=2, cur=[3, 5] // 第 1 位选择 5

[I] idx=0, i=2, ni=5, startIdx=0, startNum=2, cur=[5]
[I] idx=1, i=0, ni=2, startIdx=0, startNum=2, cur=[5, 2]
[I] idx=2, i=0, ni=2, startIdx=0, startNum=2, cur=[5, 2, 2]
[I] idx=2, i=1, ni=3, startIdx=0, startNum=2, cur=[5, 2, 3]
[I] idx=2, i=2, ni=5, startIdx=0, startNum=2, cur=[5, 2, 5]
[I] idx=1, i=1, ni=3, startIdx=0, startNum=2, cur=[5, 3]
[I] idx=1, i=2, ni=5, startIdx=0, startNum=2, cur=[5, 5]

ret: [[2, 2, 2, 2], [2, 3, 3], [3, 2, 3], [3, 3, 2], [3, 5], [5, 3]]

可以看到在第 0 位选择了 3 的时候，第 1 位有 [2, 3, 5] 三种选择，最终的结果集中有 [2, 3, 3] 和 [3, 2, 3] 两个重复的结果。

https://leetcode.com/problems/combination-sum-ii/ 该题的变种 LeetCode 40，要求不能使用重复数字，那么每次 DFS 时，需要将起始位置 +1：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(ret, new ArrayList<Integer>(), candidates, target, 0);
        return ret;
    }
    
    private void backtracking(List<List<Integer>> ret, List<Integer> cur, int[] candidates, int target, int start) {
        if (target < 0) return;
        if (target == 0) {
            ret.add(new ArrayList<>(cur));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                //System.out.println("skip, i = " + i + " start = " + start);
                continue;
            }
            cur.add(candidates[i]);
            //System.out.println("[I] start = " + start + " i = " + i + " cur = " + cur);
            backtracking(ret, cur, candidates, target - candidates[i], i + 1);
            cur.remove(cur.size() - 1);
            //System.out.println("[O] start = " + start + " i = " + i + " cur = " + cur);
        }
    }
}

执行过程如下：

[I] idx=0, i=0, ni=2, startIdx=0, startNum=2, cur=[2] // 第 0 位选择 2
[I] idx=1, i=1, ni=3, startIdx=1, startNum=3, cur=[2, 3] // 第 1 位选择 3，不能选 2 了
[I] idx=2, i=2, ni=5, startIdx=2, startNum=5, cur=[2, 3, 5] // 第 2 位选择 5，不能选 3 了
[I] idx=1, i=2, ni=5, startIdx=1, startNum=3, cur=[2, 5]  // 第 1 位选择 5
[I] idx=0, i=1, ni=3, startIdx=0, startNum=2, cur=[3]  // 第 0 位选择 3
[I] idx=1, i=2, ni=5, startIdx=2, startNum=5, cur=[3, 5] // 第 1 位选择 5
[I] idx=0, i=2, ni=5, startIdx=0, startNum=2, cur=[5]  // 第 0 位选择 5

ret: [[3, 5]]

LeetCode 51. N-Queens

如果按普通的 DFS 来搜索的话，需要搜索出所有分支，搜索树是这样的（这里实际上已经剪去了其他分支，只保留了每行只放一个的分支）：

																	root
                                  /  \
                                 /    \
                                /			 \
(第1行)第1个queen          		第1列 ... 第9列
          										/  \
                             /    \
                            /      \
(第2行)第2个queen					第1列 ... 第9列

...

实际上可以看到第 1 行第 1 列 -> 第 2 行第 1 列这个分支就已经可以剪掉了，后面已经不需要遍历了。

DFS 方案生成： 该题与 LeetCodeCNOffer 38 很像：先固定第 1 行皇后位置（有 N 种情况）、再固定第 2 行皇后位置（N - 1种情况）、... 、最后固定第 n 行皇后位置（ 1 种情况）

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ret = new ArrayList<>();
        int[] status = new int[n];
        backtracking(ret, status, 0, n);
        return ret;
    }
    
    /**
    * 
    * @param ret
    * @param status 记录当前遍历的每个皇后放置位置
    * @param curRow
    * @param n
    */
    private void backtracking(List<List<String>> ret, int[] status, int curRow, int n) {
        if (curRow == n) {
            List<String> tmp = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (status[i] == j) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                tmp.add(sb.toString());
            }
            ret.add(tmp);
            return;
        }
        
        // 对于该行每一列放置皇后的情况
        // 实际上因为前x列都放置了皇后在不同列，这里只能有 n - x 种情况是符合条件的，
        // 但是不能像LeetCodeCNOffer 38和LeetCode 39一样直接排除掉，所以要先放进去再check。
        // 因此这里的循环仍然是 [0, N)
        for (int j = 0; j < n; j++) {
            if (check(status, curRow, j)) {
                status[curRow] = j;
                backtracking(ret, status, curRow + 1, n);
                status[curRow] = -1;
            }
        }
    }
}

LeetCode 37. Sudoku Solver

该题与前面几题的区别在于 DFS 树稍微有点不同，不再是一个变量，而是两个变量决定。

DFS 方案生成： 先固定第 1 行第 1 列的数字（有 0-9 共 10 种情况），再固定第 1 行第 2 列的数字（0-9 共 10 种情况），...，固定第 1 行第 N 列的数字（共 10 种情况），固定第 2 行第 1 列的数字（共 10 种情况），...，固定第 N 行第 N 列的数字（10 种情况） 可以看到每次又行列两个变量决定，实际上这里 DFS 的时候每次仍然只有一个变量在变化。

如何构造回溯函数 ？

没有剪枝的 DFS 实际上是全排列组合，只要画出 DFS 树，找到递归终止条件，就很简单了。 一个通用的 backtracking 函数如下所示：

func backtracking(c, res) {
		if(end(c)) { // 递归终止条件
    		output(res) // 输出一个结果集
        return
    }
    
    // 遍历每一种情况，然后对不符合条件的情况做剪枝
    for (int i = 0; i <= N; i++) {
    			// 剪枝
    			if (!check_valid()) continue;
    			res.add(v(i));
          backtracking(next(c), res); 开始下一次递归
          res.del(v(i))
    }
}
  • **
    • LeetCodeCNOffer 38：length(即 idx) = N
    • LeetCode 39. Combination Sum：target_sum <= target
    • LeetCode 51. N-Queens：row = N
    • LeetCode 37. Sudoku Solver：row = N，col = N

递归终止条件是需要随着 backtracking 函数一直传递下去的

  • 每个位置遍历的情况数量（即for循环的范围）

    • LeetCodeCNOffer 38：N - idx（实际上这里完全可以是从 0 到 N 遍历，然后进 for 循环后把 [0, idx] 范围的情况剪枝）
    • LeetCode 39. Combination Sum：N - start（实际上这里完全可以是从 0 到 N 遍历，然后进 for 循环后把 [0, start] 范围的情况剪枝）
    • LeetCode 51. N-Queens：N
    • LeetCode 37. Sudoku Solver：10

  • 剪枝的条件

    • LeetCodeCNOffer 38：set.contains(s[i])
    • LeetCode 39. Combination Sum：[0, start] 范围内的数字
    • LeetCode 51. N-Queens：check(status, curRow, j)
    • LeetCode 37. Sudoku Solver：row[i][chInt] && !col[j][chInt] && !box[nineIndex][chInt]