Backtracking

If the required function does not accept more parameters that we need, we can create a helper() function to help us :) like the name

a helper function that accepts more parameters
extra params can represent current state, previous choices etc.

returnType functionName(params) {
    // blablabla
    return helper(params, moreParams);
}

returnType helper(params, moreParams) {
    // blabla
}

Backtracking

Finding solution(s) by trying solutions and then abandoning them if they are not suitable.

a “brute force” algorithm technique -> (try all possible solutions)
often implemented recursively

Applications:

permutations
parsing languages
anagrams, crosswords, word jumbles, 8 queens
…

Backtracking algorithms

A general pseudo-code algorithm for backtracking problems:

Explore(decisions):
    if (there are no more decisions to make) {
        stop
    } else {
        for (each available choice C for this decision) {
            Choose C
            Explore the remaining decisions that follow C
            Un-choose C (backtrack!!!!)
        }
    }

Summary

什么时候用回溯法?

如果题目要求求出所有满足条件的解，一般来说是用回溯法，记住回溯法的模板，对不同的题目只需要修改这个条件即可。  

回溯法的本质是在问题的解空间树上做深度优先搜索（DFS）。这节课主要讲了四个排列组合的问题，分别是子集，带重复元素的子集，全排列，带重复元素的全排列。本文分析求子集的问题，给出程序模板。

题目1：给定一个含不同整数的集合，返回其所有的子集。

样例：

如果 S = [1,2,3]，有如下的解：

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

代码：

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        helper(nums,results,new ArrayList<Integer>(),0);
        return results;
    }

    // helper function
    public void helper(int[] nums,
                       List<List<Integer>> res,
                       List<Integer> cur,
                       int start){
        List<Integer> subset = new ArrayList<Integer>(cur);
        res.add(subset);
        
        for(int i=start;i<=nums.length-1;i++){
            // choose
            cur.add(nums[i]);
            
            // explore
            helper(nums,res,cur,i+1);
            
            // un-choose
            cur.remove(cur.size()-1);
        }
    }
}