本文首發公眾號：小碼A夢

回溯演演算法是一種常見的演演算法，常見用於解決排列組合、排列問題、搜尋問題等演演算法，在一個搜尋空間中尋找所有的可能的解。通過向分支不斷嘗試獲取所有的解，然後找到合適的解，找完一個分支後再往回搜尋。回溯演演算法通常使用遞迴的方式實現。

回溯本質是一種暴力搜尋法，列出所有可能的解，然後找到合適的解。以 a、b、c的排列組合為例，畫出全排列組合。

以上排列組合回溯步驟：

• 列出所有可能存在的組合。
• 分解組合，把問題分解多個階段，每個階段新增一個分叉。
• 走完一個分叉，或者遇到不符合期望條件的時，就退回到上一個分叉。繼續走其它沒走的路。直到走完所有的路。
• 回溯一半都是使用遞迴實現。

根據以上的步驟得出一個簡單的回溯演演算法的模板：

public Solution {
   List<List<Integer>> result;

   LinkedList<Integer> path;
   
   //記錄那些元素被遍歷過
   boolean[] used;

   private List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        path = new LinkedList<>();
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums) {
        if (遞迴終止條件) {
            result.add(new ArrayList<>(path));
            return;
        }
	    //遍歷各個元素
        for (int i = 0; i < nums.length; i++) {
            used[i] = true;
	        //選擇元素
            path.add(nums[i]);
            permuteHelper(nums);
	        //移除元素
            path.removeLast();
            used[i] = false;
        }
    }
}

以上程式碼使用遞迴，遞迴一般要設定一個終止條件，然後遍歷整個元素，通過連結串列選擇元素和移除元素。

LeetCode 題解

上面所說的，回溯主要解決一些排列組合、排列問題、搜尋問題等問題，LeetCode 有很多類似的問題，這裡選取了幾個比較常見的題目。

• 39 組合總和
• 40 組合總和 II
• 46 全排列
• 47 全排列 II
• 51 N皇后

39.組合總和（中等）

題目描述

解法

這是一個比較典型的排列組合問題，本題採用的是求總和，使用總和減去遍歷的資料，最後得到結果為零，就是符合的組合。

• 為了減少遍歷次數，陣列需要先排序。總數減的資料如果小於零，就不會在該分支繼續遍歷了。
• 可以重複使用元素，每次都遍歷一遍全部元素。
• 減去分支結果之後，以新的結果，再建立分支做減法。
• 遞迴遍歷一直到結果為零和負數。
  • 為零，符合條件，記錄資料，對應的分支遍歷終止，繼續遍歷下一個分支。
  • 為負數，返回到上一個分支，繼續遍歷後面的分支。

最終程式碼：

class Solution {

    List<List<Integer>> list = new ArrayList<>();

    int[] candidate;
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        candidate = candidates;
        recall(0,target,new LinkedList<>());
		return list;
    }

    private void recall(int start, int target, LinkedList<Integer> path) {
		if (target == 0) {
			list.add(new ArrayList<>(path));
			return;
		}
		for (int i = start; i <candidate.length ; i++) {
			int sub = target - candidate[i];
			if (sub < 0) {
				break;
			}
			path.add(candidate[i]);
			recall(i,sub,path);
			path.removeLast();
		}
	}
}

recall 使用遞迴方法遍歷分支，而使用連結串列的特性，記錄遍歷的節點，如果不符合要求就上一個分支回撤，同時連結串列移除最後一個結點。

40.組合總和II（中等）

解題思路

這題的解題思路和上面的組合總和是差不多的，唯一不同的是元素不能被重複遍歷，使用一個變數記錄遍歷的起始值，遍歷過的資料，下次往後一位開始遍歷。

程式碼如下：

class Solution {

    List<List<Integer>> list = new ArrayList<>();

	int[] candidate;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
		candidate = candidates;
		recall(0,target,new LinkedList<>());
		return list;
    }

    private void recall(int start, int target, LinkedList<Integer> path) {
	if (target == 0) {
		list.add(new ArrayList<>(path));
		return;
	}
	for (int i = start; i <candidate.length ; i++) {
	    //這裡解決集合重複問題 
		if (i > start && candidate[i] == candidate[i-1]) {
			continue;
		}
		int sub = target - candidate[i];
		if (sub < 0) {
			break;
		}
		path.add(candidate[i]);
		recall(i + 1,sub,path);
		path.removeLast();
	}
     }
}

start 記錄遍歷的起始值，其他解題方法和上面的組合求和是類似的。題目還有一個要求是不能出現重複的組合，就需要判斷 candidate[i] == candidate[i-1] 就忽略該資料，往後繼續遍歷。

46.全排列

解題思路

• 每個元素都需要遍歷一遍。
• 遍歷元素的時，遍歷完第一數，繼續遍歷未遍歷的資料。
• 遍歷結束後，返回上一個分叉。

程式碼整理如下：

class Solution {
    List<List<Integer>> result = new ArrayList<>();

    LinkedList<Integer> path = new LinkedList<>();

    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

使用 used 記錄哪些資料遍歷過，遍歷過的資料不會遍歷，其他也是使用遞迴搜尋。

51.N皇后

題目描述

解題思路

N 皇后問題是一個經典的回溯演演算法問題,是面試比較常見的問題。在一個 n * n 的棋盤上，每個格子放入的元素後，檢視是夠有同行、同列、左上方以及右上方是否衝突，衝突就回溯，不衝突就繼續往下遍歷。

• 初始化陣列，預設初始值。
• 每一行只能放一個 Q,不衝突後，再遍歷下一列的資料（因為同一行不能衝突）。
• 因為每一行只放一個 Q，所以不存在同行衝突。判斷衝突就潘丹同一列、左上方以及右上方是否有衝突。
• 遍歷到最後一行時，記錄符合條件的資料。

class Solution {

    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        // 初始化棋盤 "." 表示空，"Q"表示皇后，
		char[][] board = new char[n][n];
		for (char[] c : board) {
			Arrays.fill(c, '.');
		}
		backtrack(board, 0);
		return res;
    }

    private void backtrack(char[][] board, int row) {
		//終止條件
		if (row == board.length) {
			res.add(charToList(board));
			return;
		}
		//每一行列數(也就是長度)
		int n = board[row].length;
		for (int col = 0; col < n; col++) {
			//排除相互攻擊的格子
			if (!isValid(board,row,col)) {
				continue;
			}
			//放入Q
			board[row][col] = 'Q';
			//進入下一行放皇后
			backtrack(board,row + 1);
			//復原Q
			board[row][col] = '.';
		}
   }

   private boolean isValid(char[][] board, int row, int col) {
		int n = board.length;
		//檢查列是否有皇后衝突
		for (int i = 0; i < n; i++) {
			if (board[i][col] == 'Q') {
				return false;
			}
		}
		//檢查右上方是否有皇后衝突
		for (int i = row - 1,j = col + 1; i >= 0 && j < n; i--,j++) {
			if (board[i][j] == 'Q') {
				return false;
			}
		}
		//檢查左上方是否有皇后衝突
		for (int i = row - 1,j = col - 1; i >= 0 && j >= 0; i--,j--) {
			if (board[i][j] == 'Q') {
				return false;
			}
		}
		return true;
	}

	public List<String> charToList(char[][] board) {
		List<String> list = new ArrayList<>();
		for (int i = 0; i < board.length; i++) {
			list.add(String.copyValueOf(board[i]));
		}
		return list;
	}
}

總結

回溯演演算法嘗試在問題的解空間中搜尋可能的解，並在搜尋過程中進行選擇、復原選擇和終止搜尋，直到找到解或確定無解為止。

• 通常通過遞迴函數來實現回溯演演算法。
• 在每一步，需要做出選擇（選擇一個分支）然後遞迴地探索該選擇的結果。
• 在遞迴返回後，需要復原之前的選擇，以便繼續探索其他分支。
• 使用條件語句或迴圈來控制選擇的範圍和條件。