5. 分治和回溯

1. 分治

    public void divideConquer(int problem, int param) {
        // recursion terminator
        if (problem == null) {
            return;
        }
        // prepare data
        data = prepareDate(problem);
        subProblems = splitProblem(problem, data);
        // conquer sub problems
        subResult1 = divideConquer(subProblems[0], param);
        subResult2 = divideConquer(subProblems[1], param);
        subResult3 = divideConquer(subProblems[2], param);
        subResult4 = divideConquer(subProblems[3], param);
        // ...
        result = processResult(subResult1, subResult2, subResult3, subResult4);
        // revert thr current level states.
    }

1.1 pow(x,n) （50）

• 解法1: 循环

• 解法2: 分治

• 解法3: 牛顿迭代法

2. 回溯

2.1 子集（78）

• 解法1:

2.2 众数

2.3 电话号码的字母组合（17）

• 解法1: 递归

• s

2.4 N皇后问题