關于回溯的那些事

在lc刷題過程中，有一類題都可以用到回溯的思想處理，比如全排列、子集、組合、分割回文串等。網上有很多關于回溯算法的簡單解釋，比較容易入門，簡單解釋就是把所有的可能都試探一遍，成功的就記錄下來，不成功的就傳回上一次試探路徑繼續往其他方向試探，直到所有可能都嘗試過，傳回符合要求的記錄。下面針對一些問題總結下這類問題如何統一解決。

首先列出解決該類問題的通用模版，看不懂無所謂，後面會根據例題逐一解釋

public List<List<Integer>> backtracking(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        // 非必須，要求去重時需要
        Arrays.sort(candidates);
        this.recursion(candidates, 0, target, new ArrayList<>(), ans, new boolean[candidates.length]);
        return ans;
    }

	/**
     * 遞歸函數
     * @param nums 給定的數組，也可能是int n
     * @param start   非必須，每次循環的起始位置，防止數字重複使用
     * @param remained  非必須，有些題目會給定目标值，sum隻和等于目标值之類的
     * @param list  臨時list，存儲部分結果集
     * @param ans 結果集
     * @param used 非必須，去重複所需
     */
    private void recursion(int[] nums, int start, int remained, List<Integer> list, List<List<Integer>> ans, boolean[] used) {
        if (remained == 0) {
            ans.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < nums.length; i++) {
                if (remained < nums[i]) {
                    break;
                }
                if (i > start && nums[i] == nums[i-1]) continue;
                list.add(nums[i]);
                recursion(nums, i+1,remained - nums[i], list, ans, used);
                list.remove(list.size()-1);
            }
        }
    }
           

一、先看lc78題：

給定一組不含重複元素的整數數組 nums，傳回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集。

示例:

輸入: nums = [1,2,3]

輸出:

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

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        recursion(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    private void recursion(int[] nums, int start, List<Integer> list, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(list));
        for (int i=start; i<nums.length; i++) {
            list.add(nums[i]);
            recursion(nums, i+1, list, ans);
            list.remove(list.size()-1);
        }
    }
           

這是最簡單的回溯處理，給定數列無重複，結果集不重複。

二、lc90

給定一個可能包含重複元素的整數數組 nums，傳回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集。

示例:

輸入: [1,2,2]

輸出:

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

public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        recursion(nums, 0, new ArrayList<>(), ans, new boolean[nums.length]);
        return ans;
    }

    private void recursion(int[] nums, int start, List<Integer> list, List<List<Integer>> ans, boolean[] used) {
        ans.add(new ArrayList<>(list));
        for (int i=start; i<nums.length; i++) {
            if (!used[i]) {
                // 去重複
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                used[i] = true;
                list.add(nums[i]);
                recursion(nums, i + 1, list, ans, used);
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }
           

這題比之前不一樣的地方是給定數列有重複，處理上多了幾個地方

1.首先對給定數組排序

2.增加去重複的判斷語句

3.增加是否已經使用過的變量存儲。

下面着重解釋下2、3點，第1點是因為排序後友善對重複資料進行處理。

第2點， if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) 說明：因為第一個數不可能有重複，是以跳過隻有一個數的情況，中間的相等不多解釋了。後面的這個比較難了解，為什麼是前一個數字沒有被使用的時候，選擇跳過，這是因為在循環體裡的規定首先給數組進行标示，然後遞歸，然後回溯。當上一個數字被标記為沒有使用的意思就是這個循環處在回溯的情況下，相當于之前肯定有一次循環處理了使用的情況，這裡再處理就多餘了。另外for循環裡還有一層是!used[i]的判斷，是便于看，為了簡潔可以和整體if合并到一起，變為if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1])。

三、lc40

給定一個數組 candidates 和一個目标數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中隻能使用一次。

說明：

所有數字（包括目标數）都是正整數。

解集不能包含重複的組合。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,

所求解集為:

[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> ansOne = new ArrayList<>();
        Arrays.sort(candidates);
        this.recursion(candidates, 0, target, ansOne, ans, new boolean[candidates.length]);
        return ans;
    }

    private void recursion(int[] nums, int start, int remained, List<Integer> list, List<List<Integer>> ans, boolean[] used) {
        if (remained == 0) {
            ans.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < nums.length; i++) {
                // 循環中判斷，減少一次遞歸
                if (remained < nums[i]) {
                    break;
                }
                if (i > start && nums[i] == nums[i-1]) continue;
                list.add(nums[i]);
                recursion(nums, i+1,remained - nums[i], list, ans, used);
                list.remove(list.size()-1);
            }
        }
    }
           

與之前的類似，多增加了目标值，每次遞減，直至為0即可。過程中可以對減到負數的做剪支處理。判斷去重複的條件改成了if (i > start && nums[i] == nums[i-1])，start是遞歸函數的參數，意思就是說第一次循環的時候可以用該值。

四、其他題目，都是可以套用模版

比如77、39、46、47、216等，下面對比下模版中的不同配置參數的意義

// 1. 判斷去重的語句
// a 當給定數列中有重複資料，部分結果集中不能有相同值
if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
// b 給定數列有重複資料，結果集中不能有重複的list資料（位置不對，值一樣）
 if (i > start && nums[i] == nums[i-1])

// 2.循環的範圍
a. int i = start   從給定數列順序往下執行，不允許回退
b. int i = 0    給定的數列可以随意選擇

// 3.遞歸start參數
a. 向遞歸函數傳遞目前值i：數列中值可以無限次重複使用
b. 向遞歸函數傳遞i+1：每個值隻能使用1次