131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

回文分割系列是一个经典系列，这是系列的第一道，也是一个经典回溯法问题。

我花了不少时间才写出来，而且我肯定有更好的写法，不过现在回溯也成为我的技能了。

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const r = []
    if (isPalindrome(s)) {r.push([s])}

    
    function backtracking(s, start, partitions) {
        for (let i=start+1; i<s.substring(s).length; i++) {
            partitions.push(s.substring(start, i))
            partitions.push(s.substring(i))
            if (partitions.every(isPalindrome))
                r.push(partitions.slice())
            partitions.pop()
            backtracking(s, i, partitions)
            partitions.pop() 
        }
    }
    
    backtracking(s, 0, [])
    
    function isPalindrome(s) {
        let left=0, right=s.length-1
        
        while(s.charAt(left) === s.charAt(right)) {
            if (left === right || Math.abs(left - right) === 1) {
                return true
            }
            left++
            right--
        }
        return false
    }
    
    return r
};

回溯是一种使用递归进行暴力枚举的方式。其特点是：在循环递归的时候，会先推入某个值，然后进行递归，然后再推出某个值——也就是回溯。考虑到它解决问题的方式这是很自然的。因为是枚举，所以需要在当前循环中依次遍历；同时为了递归，又要加上下一个值，否则就无法进行下一层循环了。于是就有了这样的结构：先推一个值，然后递归，结束后弹出刚才的值。这样在下一轮循环中，可以推入一个新的值，进行新一轮的递归。

具体到这一题，因为每次分割会产生两个子串，所以我分了两次。但是，这一题明显有优化点：如果我发现有一处不是回文了，就没有必要再继续了。

---

78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

这题比上一题来的简单。实际上寻找所有子情况基本上算是洄溯问题的基本母题了，所以这一题可以看作回溯问题的基本型。不过我还是挺喜欢这一题的。它的写法可以有很多细节变化，蛮能体现一个人的编程习惯的。单纯就 backtrack 的入参就可以有很多种。

下面是个人写法。由于函数副作用很强，所以个人很不喜欢这个实现。【update： 这个解法很糟糕，详见我下一题解释。】比较简洁优雅的实现可以看这个：Javascript Simple Solution ( Backtrack )

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let rst = [[]], suffix = []

    function backtrack(arr) {
        if (suffix.length > nums.length) return 

        for (let i=0; i<arr.length; i++) {
            suffix.push(arr[i])
            rst.push(suffix.slice())
            backtrack(arr.slice(i+1))
            suffix.pop()
        }
    }
    
    backtrack(nums, [])
    
    return rst
};

---

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• All elements of candidates are distinct.
• 1 <= target <= 500

这是第三道回溯题了。现在我对回溯问题有点适应了。

现在我觉得掌握回溯的关键在于明白递归过程中到底发生了什么。而这只有通过做题才能促进思考，通过思考然后形成一种『感觉』。

现在，我可以发现回溯问题中，backtrack 的入参是个很有趣的点。它通常至少会有这两个参数：

1. 递归中的子项。可以是子字符串，或者是搜索中的子序列。它们会随着一次次递归而变长（或者变短）。回溯本质是一个暴力算法，子项必然会把所有情况都经历一遍。
2. 当前的位置。这很重要，你必须记录你已经遍历到第几层了，然后才能加入合适的元素。上一题（78）的代码截取字符串来变相实现了这一点，其实是非常不好的写法，因为这样很不直观。可以说这是我当时还没有掌握回溯的证明。
3. 我发标准的算法常常会把原数组或者字符串也带上。我认为对于js写法这是可以省略的。当然它的好处显而易见：传入后 backtrack 就成了纯函数。

需要注意的是，如果是用一个数组储存所有可能的结果，那么在搜集可能的值的时候，需要创建一份 clone ，这算是一个坑

我认为这题我解得还不错 :-)

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let rst = []
    
    backtrack([], 0, 0)
    
    return rst
    
    function backtrack(arr, sum, start) {
        if (sum === target)
            rst.push(arr.slice())
        if (sum >= target)
            return
        for (let i=start; i<candidates.length; i++) {
            arr.push(candidates[i])
            backtrack(arr, sum + candidates[i], i)
            arr.pop()
        }
    } 
};

另外，这题有人写了很好的题解，整理了大量 leetcode 回溯问题的范式，值得一看：A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)