Backtracking Template -- General Approach (DFS)

何時使用:

1. 需要搜尋所有可能答案的時候

2. 需要暴力破解的時候

有一個重點是通常backTracking 的case會發生在乍看之下DP可以解, 但其實簡化問題的過程存在諸多變數而無法直截了斷的簡化, 我們無法很主觀的判斷, 哪種簡化方式才適合的做法時, 就只能使用暴力破解

n-queen problem:O(n!)

graph coloring problem:O(nm^n)//where n=no. of vertex,m=no. of color used

hamilton cycle:O(N!)

WordBreak and StringSegment:O(2^N)

subset sum problem:O(nW) 具體作法

定義每一Run 3 Steps 1. Choose: 針對每個選擇，先假設選擇了，若此時有特殊條件要滿足，則需先判斷，若不滿足條件就不用選了。 2. Observe: 針對Choose後所剩餘的子問題做遞迴，此時會需要一個heper function，幫助做遞迴。 3. Unchoose: Undo之前的Choose，進入到下個選擇，並重複上述步驟 考慮何時tempResult可以更新到finalResult? 若滿足

isTempResultIsCompletedThisRun

才可加入finalResult

About Helper's parameters: 1. data The data we are working on (usually list or array) 2. finalResult The final return data 3. tempResult The temp result data we got during recursion 4. start, end, index ...etc (optional) Something help us to narrow main-quest to sub-quest, might not present if no need.

TimeComplexity: O(n*2^n), where n is the nums.length. * 2^n for recursion (either choose/unchoose for maximum n elements), * And for each iteration, take n for cloning the tempResult into finalResult.

Template:

public ArrayList<List<>> mainQuestion(int[] inputs){
    ArrayList<List<>> ret = new ArrayList<>(); //the final result
    helper(inputs, ret, new Arraylist<Integer>(), 0)
    return ret;
}

public void helper(int[] data, ArrayList<List<>> finalResult, 
                                    List<> tempResult, int index){

    if(isTempResultIsCompletedThisRun){
        finalResult.add(new ArrayList<>(tempResult)); //clone the tempResult,
        //tempResult is a refernce in finalResult, so if we the change its value in other run
        //the finalResult will be impacted too. therefore we must clone the tempResult 
    }
    //create a loop to consider each possibilities
    for(int i = index; i < data.length; i++){
            if(isfullfieldCondition(data[i]){
                tempResult.add(data[i]); //choose
                helper(data, finalResult, tempResult, index++); // observe
                tempResult.remove(tempResult.size()-1); //unchoose
                //unchoose remove the last item of tempResult is same as remove data[i]
                //To avoid duplicated item in tempResult, remove the last item is more safe.
            }
    }

}

Example : SubSet