回溯法

回溯法的套路解法在这篇文章中给了详细的说明。

岛屿数量

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

图的深度优先遍历，将 1 置为 0

public int numIslands(char[][] grid) {
    int num = 0;

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == '1') {
                num++;
                mark(grid, i, j);
            }
        }
    }

    return num;
}

private void mark(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || 
            j < 0 || j >= grid[i].length ||
            grid[i][j] == '0') {
                return;
    }

    grid[i][j] = '0';

    mark(grid, i + 1, j);
    mark(grid, i - 1, j);
    mark(grid, i, j + 1);
    mark(grid, i, j - 1);
}

Subsets

返回一个数组的所有 subsets:

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

解法：

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));

    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

如果这个数组中有重复的数字，那么下面算法展示的是去掉重复数字的写法：

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));

    for (int i = start; i < nums.length; i++){
        if (i > start && nums[i] == nums[i-1]) 
        	continue; // skip duplicates

        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

全排列

对于全排列 (Permutations)：

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

它的套路写法如下：

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if (tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for (int i = 0; i < nums.length; i++){ 
         if (tempList.contains(nums[i])) 
         	continue; // element already exists, skip

         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
}

但是这样子写，这个 contains 方法的复杂度是 O(n)，所以也可以使用 HashSet 来优化：

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    backtrack(ret, new ArrayList<>(), new HashSet<>(), nums);
    return ret;

}

private void backtrack(List<List<Integer>> ret, List<Integer> tmpList, Set<Integer> tmpSet, int[] nums) {
    if (tmpSet.size() == nums.length) {
        ret.add(new ArrayList<>(new ArrayList<>(tmpList)));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (tmpSet.contains(nums[i])) 
        	continue;
        
        tmpSet.add(nums[i]);
        tmpList.add(nums[i]);
        
        backtrack(ret, tmpList, tmpSet, nums);
        
        tmpSet.remove(tmpList.get(tmpList.size()-1));
        tmpList.remove(tmpList.size() - 1);
    }
}

如果它的数组也是包含重复的，那么去掉重复数字的全排列写法如下，我们这个地方还有技术债，那就是 if 条件为什么要这样写：

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if (tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for (int i = 0; i < nums.length; i++){
            if (used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) 
            	continue;

            used[i] = true; 
            tempList.add(nums[i]);

            backtrack(list, tempList, nums, used);
            
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}

Combination Sum

找到所有加起来等于某个 target 的候选解法，数组中无重复数字：

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

它的解法如下：

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if (remain < 0) {
    	return;
    } else if (remain == 0) {
    	list.add(new ArrayList<>(tempList));
    } else { 
        for (int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

下面是数组中一个数字只能使用一次的版本：

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if (remain < 0) {
    	return;
    } else if(remain == 0) {
    	list.add(new ArrayList<>(tempList));
    } else{
        for (int i = start; i < nums.length; i++){
            if (i > start && nums[i] == nums[i-1]) 
            	continue; // skip duplicates

            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
}

生成括号

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

// 时间复杂度，总的括号对个数是 Catalan number 个
// O(C(2n, n) / (n + 1))
public List<String> generateParenthesis(int n) {
    List<String> res = new LinkedList<>();
    helper(res, "", 0, 0, n);
    return res;
}

private void helper(List<String> res, String cur, int open, int close, int n) {
    if (open == n && close == n) {
        res.add(cur);
        return;
    }

    if (open < n) {
        helper(res, cur + "(", open + 1, close, n);
    }

    if (close < open) {
        helper(res, cur + ")", open, close + 1, n);
    }
}

添加不同括号的方式

// 头条面试题
//
// https://leetcode.com/problems/different-ways-to-add-parentheses/
// Input: "2*3-4*5"
// Output: [-34, -14, -10, -10, 10]
// Explanation: 
// (2*(3-(4*5))) = -34 
// ((2*3)-(4*5)) = -14 
// ((2*(3-4))*5) = -10 
// (2*((3-4)*5)) = -10 
// (((2*3)-4)*5) = 10
//
// 只有 +、- 和 *
//
// 有几种不同的结果
public class DifferentWaysToAddParentheses {

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> ret = new LinkedList<Integer>();

        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '-' ||
                input.charAt(i) == '*' ||
                input.charAt(i) == '+' ) {
                
                String part1 = input.substring(0, i);
                String part2 = input.substring(i + 1);

                List<Integer> part1Ret = diffWaysToCompute(part1);
                List<Integer> part2Ret = diffWaysToCompute(part2);

                for (Integer p1:part1Ret) {
                    for (Integer p2:part2Ret) {
                        int c = 0;
                        switch (input.charAt(i)) {
                            case '+': c = p1 + p2;
                                break;
                            case '-': c = p1 - p2;
                                break;
                            case '*': c = p1 * p2;
                                break;
                        }
                        ret.add(c);
                    }
                }
            }
        }

        if (ret.size() == 0) {
            // input 是一个单一数字
            ret.add(Integer.valueOf(input));
        }

        return ret;
    }

}

目标和

给定一个非负整数的列表a1,a2,…an，再给定一个目标 S。现在用+和-两种运算，对于每一个整数，选择一个作为它前面的符号。

找出有多少种方法，使得这些整数的和正好等于 S。

输入: nums为 [1, 1, 1, 1, 1], S 为 3. 
输出: 5
解释: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

有5种方法让和为3.

题解：

class Solution {
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    public void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}

复杂度分析

时间复杂度：O(2^n)，其中 n 是数组数组的长度。回溯需要遍历所有不同的表达式，共有 2^n 种不同的表达式，每种表达式计算结果需要 O(1) 的时间，因此总时间复杂度是 O(2^n)。

空间复杂度：O(n)，其中 n 是数组的长度。空间复杂度主要取决于递归调用的栈空间，栈的深度不超过 n。