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

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

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

針對(duì)所給問題得出一般的解空間

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

使用深度優(yōu)先去搜索所有解并包含適當(dāng)?shù)募糁Σ僮?/p>

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 出定長(zhǎng) int array 中所有子集合，使用回溯算法遍歷定長(zhǎng) array，然后回溯來選擇出所有可能的組合.

針對(duì) backTrack 時(shí)間復(fù)雜度的分析直接復(fù)習(xí)結(jié)果集的大小有效

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++) {
        //每次加下一個(gè)index的element
        temp.add(nums[i]);
        //深度優(yōu)先到下一層
        helper(nums, res, i + 1, temp);
        //backTracking
        temp.remove(temp.size() - 1);
    }
}

針對(duì)如果輸入數(shù)組有重復(fù)的元素，但是要求輸出的結(jié)果沒有重復(fù)，可以一些去重的方法并注意防止溢出

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>();
    //對(duì)input數(shù)組進(jìn)行排序，準(zhǔn)備為數(shù)組進(jìn)行去重
    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++) {
        //去重復(fù)，并且防止溢出
        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一個(gè)定長(zhǎng)數(shù)組，要求找到所有子數(shù)組集合以至于子數(shù)組所有數(shù)的和等于目標(biāo)數(shù)，可以運(yùn)用回溯算法，區(qū)間為given的定長(zhǎng)數(shù)組

Solution:

同樣是用回溯的方法，但是針對(duì)數(shù)組中子數(shù)可以重復(fù)使用
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, 因?yàn)樾枰貜?fù)使用所以遞歸調(diào)用i 沒有變化
        helper(candidates, target - candidates[i], res, temp, i);
        temp.remove(temp.size() - 1);
    }
}

變種，針對(duì)CombinationSum 數(shù)組中子數(shù)只可以被使用一次:
時(shí)間復(fù)雜度仍然為O(2^n), 空間復(fù)雜度為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++) {
                //進(jìn)行防溢出和去重
                if(i != index && candidates[i] == candidates[i - 1]) continue;
                temp.add(candidates[i]);
                //DFS dive into next level, 因?yàn)樾枰貜?fù)使用所以遞歸調(diào)用i 沒有變化
                helper(candidates, target - candidates[i], res, temp, i);
                temp.remove(temp.size() - 1);
    }
}