摘要：回溯算法在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。

回溯算法( BackTrack )在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。

使用回溯算法解題的一般步驟：

針對所給問題得出一般的解空間

用回溯搜索方法搜索解空間

使用深度優先去搜索所有解并包含適當的剪枝操作

LeetCode 使用回溯算法的題目主要有 36 題，代表性有 N Queens(51,52), SubSets(78), Permutation(46(distinct), 47(with duplicates)), Combination, Combination Sum.

SubSets:

Given a set of distinct integers, nums, return all possible subsets (the power set).

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],[]]

SubSets 這道題要求 print 出定長 int array 中所有子集合，使用回溯算法遍歷定長 array，然后回溯來選擇出所有可能的組合.

針對 backTrack 時間復雜度的分析直接復習結果集的大小有效

Runtime: O(2^n), Space: O(n)

Solution:

public List> subsets(int[] nums) {
    if(nums == null || nums.length == 0) return null;`                
    List> res = new ArrayList>();
    helper(nums, res, 0, new ArrayList<>());
    return res;       
}
    
public void helper(int[] nums, List> res, int index, List temp) {
    //考慮空子集的情況
    res.add(new ArrayList<>(temp));
    for(int i = index; i < nums.length; i++) {
        //每次加下一個index的element
        temp.add(nums[i]);
        //深度優先到下一層
        helper(nums, res, i + 1, temp);
        //backTracking
        temp.remove(temp.size() - 1);
    }
}

針對如果輸入數組有重復的元素，但是要求輸出的結果沒有重復，可以一些去重的方法并注意防止溢出

If nums = [1,2,2], a solution is
[[2],[1],[1,2,2],[2,2],[1,2],[]]

Solution:

public List> subsetsWithDup(int[] nums) {
    if(nums == null || nums.length == 0) return null;
    List> res = new ArrayList>();
    //對input數組進行排序，準備為數組進行去重
    Arrays.sort(nums);
    helper(nums, res, 0, new ArrayList<>());
    return res;
}
    
public void helper(int[] nums, List> res, int index, List temp) {
    res.add(new ArrayList<>(temp));
    for(int i = index; i < nums.length; i++) {
        //去重復，并且防止溢出
        if(i != index && nums[i] == nums[i - 1]) continue;
        temp.add(nums[i]);
        helper(nums, res, i + 1, temp);
        temp.remove(temp.size() - 1);
    }
}

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]]

這道題要求given一個定長數組，要求找到所有子數組集合以至于子數組所有數的和等于目標數，可以運用回溯算法，區間為given的定長數組

Solution:

同樣是用回溯的方法，但是針對數組中子數可以重復使用
time:O(2^n), space: O(n)

public List> combinationSum(int[] candidates, int target) {
    if(candidates == null || candidates.length == 0) return null;
    List> res = new ArrayList>();
    helper(candidates, target, res, new ArrayList(), 0);
    return res;
}

public void helper(int[] candidates, int target, List>res, List temp, int index) {
    if(target < 0) return;
    else if(taget == 0) res.add(new ArrayList(temp));
    else {
        for(int i = index; i < candidats.length; i++) {
        temp.add(candidates[i]);
        //DFS dive into next level, 因為需要重復使用所以遞歸調用i 沒有變化
        helper(candidates, target - candidates[i], res, temp, i);
        temp.remove(temp.size() - 1);
    }
}

變種，針對CombinationSum 數組中子數只可以被使用一次:
時間復雜度仍然為O(2^n), 空間復雜度為O(n)

public List> combinationSum(int[] candidates, int target) {
    if(candidates == null || candidates.length == 0) return null;
    List> res = new ArrayList>();
    helper(candidates, target, res, new ArrayList(), 0);
    return res;
}

public void helper(int[] candidates, int target, List>res, List temp, int index) {
        if(target < 0) return;
        else if(taget == 0) res.add(new ArrayList(temp));
        else {
            for(int i = index; i < candidats.length; i++) {
                //進行防溢出和去重
                if(i != index && candidates[i] == candidates[i - 1]) continue;
                temp.add(candidates[i]);
                //DFS dive into next level, 因為需要重復使用所以遞歸調用i 沒有變化
                helper(candidates, target - candidates[i], res, temp, i);
                temp.remove(temp.size() - 1);
    }
}