在 Leetcode 看到很好的一篇总结,所以我根据看到的再重新写一篇,方便自己理解

首先理解一下什么是回溯,可以用迷宫来做比喻.
通常走出一个迷宫的方法如下:

1. 进入迷宫(废话...)
2. 选一条道一直走, 一直走到有一个分岔
3. 选最左的一条道
4. 如果你走到了死胡同, 就回到之前最后一个分岔口, 选从左边数起第二条分岔.
5. 一直循环 2 - 5, 直到找到出口位置

伪代码就变成了这个样子:

start
while exist not found:
  for each path in the fork:
    check whether the path is safe
    if yes :
      select it and continue walk
  if all paths don't resolve the maze, return False
end

接下来看 Leetcode 原题

Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

class DFS:  # 也可以把 backtracking 当成 DFS
    def subsets(self, S):
        self.result = []
        self.backtrack(0, sorted(S), [])
        return self.result

        # 这个是模板啊~
    def backtrack(self, start, S, temp):
        self.result.append(temp[:])
        for i in range(start , len(S)):
            temp.append(S[i])
            self.backtrack(i + 1, S, temp)
            temp.pop()

看 follow up:

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

这题就是多加了一个判断, 去掉重复的

class DFS:
    def subsetsWithDup(self, S):
        self.result = []
        if len(S) == 0: return self.result
        self.helper(0, sorted(S), [])
        return self.result

    def backtrack(self, start, S, temp):
        self.result.append(temp[:])
        for i in range(start, len(S)):
            if i != start and S[i] == S[i - 1]: # 忽略重复的
                continue
            temp.append(S[i])
            self.helper(i + 1, S, temp)
            temp.pop()

另外一类相似的题

Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

跟前两道题的区别在于 subset 可以不包括全部.

class Solution:
    def permute(self, nums):
        self.result = []
        self.backtrack(nums, [])
        return self.result

    def backtrack(self, nums, temp):
        if len(temp) == len(nums):
            self.result.append(temp[:])
                # 由于长度一样, 所以不用知道 index,连 i 都免了
        else:
            for n in nums:
                if n in temp:
                    continue
                temp.append(n)
                self.backtrack(nums, temp)
                temp.pop()

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

一样玩法,查重复的

class DFS2:
    def permuteUnique(self, nums):
        self.result = []
        # 查重的方法改变了,通过一个数组来记录有没有走过这个位置的数
        self.backtrack(sorted(nums), [], [False for _ in range(len(nums))])
        return self.result

    def backtrack(self, nums, temp, visited):
        if len(nums) == len(temp):
            self.result.append(temp[:])
        else:
            for i in range(len(nums)):
                # 保证前一个相同的数也必须包含在结果里
                if visited[i] or (i > 0 and nums[i] == nums[i - 1]) and not visited[i - 1]:
                    continue
                visited[i] = True
                temp.append(nums[i])
                self.backtrack(nums, temp, visited)
                visited[i] = False
                temp.pop()

另一组题目

Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

class DFS:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum(self, candidates, target):
        self.result= []
        self.backtrack(sorted(candidates), target, 0, 0, [])
        return self.result

    def backtrack(self, candidates, target, start, total, temp):
        if total > target:
            return
        elif total == target:
            self.result.append(temp[:])
        else:
            for i in range(start, len(candidates)):
                temp.append(candidates[i])
                # 这里注意用的是 i 而不是 i+ 1, 原因是因为一个数可以重复利用很多次
                self.backtrack(candidates, target, i, total + candidates[i], temp)
                temp.pop()

题型变化一下, 一样是跟重复有关系
Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

class Solution:
    # @param candidates, a list of integers
    # @param target, integer
    # @return a list of lists of integers
    def combinationSum2(self, candidates, target):
        self.result = []
        self.backtrack(sorted(candidates), 0, 0, target, [])
        return self.result

    def backtrack(self, candidates, start, total, target, temp):
        if total > target:
            return
        elif total == target:
            self.result.append(temp[:])
        else:
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                temp.append(candidates[i])
                self.backtrack(candidates, i + 1, candidates[i] + total, target, temp)
                temp.pop()

接下来的题加了个限制总共可以用多少个数

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

要注意题目限制是 1 - 9, 9个数字

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        self.result = []
        if k < 0:   return []
        self.backtrack(k, n, 1, 0, [])
        return self.result

    def backtrack(self, k, n, start, total, temp):
        if total == n and len(temp) == k:
            self.result.append(temp[:])
        else:
            for i in range(start, 10):
                temp.append(i)
                self.backtrack(k, n, i + 1, i + total, temp)
                temp.pop()

至于第四题 Combination Sum IV, 包含了负数和不限制数量的条件,要用 DP 来解题, 这个以后在别的地方再提吧.
接下来的题其实都大同小异了...

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.

For example, given s = "aab",
Return

[
["aa","b"],
["a","a","b"]
]

变成了 String, 再加个回文的判定

class Solution(object):
    # @param s, a string
    # @return a list of lists of string
    def partition(self, s):
        self.result = []
        # track each possible partition
        self.backtrack(s, 0, [])
        return self.result

    def backtrack(self, s, start, temp):
        if start == len(s):
            self.result.append(temp[:])
        else:
            for i in range(start, len(s)):
                string = s[start: i + 1]
                if self.isPalindrome(string):
                    temp.append(string)
                    self.backtrack(s, i + 1, temp)
                    temp.pop()

    def isPalindrome(self, string):
        left, right = 0, len(string) - 1
        while left < right:
            if string[left] != string[right]:
                return False
            left+=1
            right-=1
        return True

Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

这道题的用法其实是一样的, 加上有效判断数字的话能快不少

class Solution:
    # @param s, a string
    # @return a list of strings
    def restoreIpAddresses(self, s):
        if len(s) < 4 or len(s) > 12:
            return []
        self.result = []
        self.backtrack(s, 0, [])
        return self.result

    def backtrack(self, s, start, temp):
        if len(temp) == 4 and start == len(s):
            self.result.append(".".join(temp))
        for i in range(start, min(start + 4, len(s))):
            string = s[start: i + 1]
            if self.isValid(string):
                temp.append(string)
                self.backtrack(s, i + 1, temp)
                temp.pop()

    def isValid(self, string):
        if not string:  return False
        if len(string) > 1 and string[0] == '0':
            return False
        return int(string) <= 255

Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.

Note:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]

相同的算法但是 Python 超时了...这个题意很简单,就是要找到除了1和自己以外有因数的解, n <= 1 && temp.size() > 1这个条件可以把1 和自己本身的数去掉.

import java.util.List;
import java.util.ArrayList;

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().getFactors(8));
    }

    private List<List<Integer>> result;

    public List<List<Integer>> getFactors(int n) {
        result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        backtrack(n, temp, 2);
        return result;
    }

    private void backtrack(int n, List<Integer> temp, int start){
        if (n <= 1 && temp.size() > 1) {
            result.add(new ArrayList<Integer>(temp));
        }else {
            for (int i = start; i < n + 1; i++) {
                if (n % i == 0) {
                    temp.add(i);
                    backtrack(n/i, temp, i);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }
}