Neetcode 150 — Backtracking
27 min readNov 4, 2026
最近為了練習刷題，開始寫 Neetcode 150。以下是我的刷題筆記，主要以 JAVA 來練習，分類及題目來自 Neetcode。
Note
- 最基本的 backtrack 雛形
以 nums = [1, 2] 為例，列出所有子集合。
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(
int[] nums,
int start,
List<Integer> path) {
// 記錄目前的子集合
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
// 1. Choose
path.add(nums[i]);
// 2. Explore
backtrack(nums, i + 1, path, result);
// 3. Undo
path.remove(path.size() - 1);
}
}
}2. 子集合，每一個選擇要或不要，如最基本的 backtrack 雛形。
Time complexity 會是 2^n，ex. 第一題，第三題，第五題，第八題
void backtrack(int[] nums, int start, List<Integer> path) {
if (...) {
return;
}
for (int i = start; i < n; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path);
path.remove(path.size() - 1);
}
}3. 子集合，每一個選擇可以選要或不要，但每一個選擇可以重複選
ex. 第二題
void backtrack(int[] nums, int start, List<Integer> path) {
if (...) {
return;
}
for (int i = start; i < n; i++) {
path.add(nums[i]);
backtrack(nums, i, path);
path.remove(path.size() - 1);
}
}4. 排列組合，每一個選擇都要被選到，但順序不一樣。
Time complexity 會是 n!，ex 第四題，第十題
private void backtrack(int[] nums, Set<Integer> set, List<Integer> path) {
if (...) {
return;
}
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
continue;
}
path.add(nums[i]);
set.add(nums[i]);
backtrack(nums, set, path);
path.remove(path.size() - 1);
set.remove(nums[i]);
}
}5. 排列組合，每一個選擇都要被選到，但選擇可以重複選
例如’(’ 和 ‘)’，Time complexity 會是 Cn = (2n!)/n!n!，ex. 第六題
private void backtrack(int left, int right, int n, StringBuilder path) {
if (left == n && right == n) {
result.add(path.toString());
return;
}
if (left < n) {
path.append("(");
backtrack(left + 1, right, n, path);
path.deleteCharAt(path.length() - 1);
}
if (right + 1 <= left) {
path.append(')');
backtrack(left, right + 1, n, path);
path.deleteCharAt(path.length() - 1);
}
}6. 走路徑，每一次都要選一個選擇，但每次的選擇項目和上次不同。
Get AShiou’s stories in your inbox
Join Medium for free to get updates from this writer.
Time complexity: 3^n，ex. 第七題，第九題
private boolean backtrack(char[][] board, int r, int c, int start, String word) {
if (start == word.length()) {
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
return false;
}
if (board[r][c] == '#') {
return false;
}
char ch = board[r][c];
if (ch != word.charAt(start)) {
return false;
}
board[r][c] = '#';
boolean found = backtrack(board, r + 1, c, start + 1, word)
|| backtrack(board, r - 1, c, start + 1, word)
|| backtrack(board, r, c + 1, start + 1, word)
|| backtrack(board, r, c - 1, start + 1, word);
board[r][c] = ch;
return found;
}1. Subsets
// 1. DFS + backtracking
// 經典的 backtracking
//
// 假設有 n 個 nums
// Time complexity: O(n*2^n)
// - recursive 時有選擇或不選擇 num -> 2^n
// - copy path: 每一個 path 都要 n
// Space copmlexity: O(n*2^n)
// - recursive depth: n
// - path: n
// - result: 這題有 2^n 個結果，每個 subset 最多有 n 個 num -> n*2^n
//
// Dry run
// nums = [1,2,3]
// backtrack(0, [])
// - backtrack(1, [1])
// -- backtrack(2, [1,2])
// --- backtrack(3, [1,2,3])
// -- backtrack(3, [1,3])
// - backtrack(2, [2])
// -- backtrack(3, [2,3])
// - backtrack(3, [3])
//
// step | start | i | path | action
// 1 | 0 | - | [] | add []
// 2 | 0 | 0 | [1] | add [1]
// 3 | 1 | 1 | [1,2] | add [1,2]
// 4 | 2 | 2 | [1,2,3] | add [1,2,3]
// 5 | 3 | - | [1,2,3] | return
// 6 | 2 | 2 | [1,2] | remove 3
// 7 | 1 | 1 | [1] | remove 2
// 8 | 1 | 2 | [1,3] | add [1,3]
// 9 | 3 | - | [1,3] | return
// 10 | 1 | 2 | [1] | remove 3
// 11 | 0 | 0 | [] | remove 1
// 12 | 0 | 1 | [2] | add [2]
// 13 | 2 | 2 | [2,3] | add [2,3]
// 14 | 3 | - | [2,3] | return
// 15 | 2 | 2 | [2] | remove 3
// 16 | 0 | 1 | [] | remove 2
// 17 | 0 | 2 | [3] | add [3]
// 18 | 3 | - | [3] | return
// 19 | 0 | 2 | [] | remove 3
//
// for loop 1-n，backtrack 後有 for loop 2-n，再下一個 backtrack 有 3-n 可以選。
//
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] nums, int start, List<Integer> path) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path);
path.remove(path.size() - 1);
}
}
}2. Combination Sum
// 1. DFS + backtrack
// nums = [2,5,6,9]
// target = 9
// 可以 for loop nums 但如果可以再加上現在的數字，就不+1，如果不行就+1
//
// 假設有 N 個 nums, T:target, M:最小的 num
// Time complexity: O(N^(T/M))
// - 每次有 T/M 個選擇 -> N^(T/M)
// - copy path -> 每次要 T/M
// Space complexity: O(N^(T/M))
// - recursive depth: T/M
// - path: T/M
// - result: 有 N^(T/M) 個結果，每個結果最多有 T/M 個數字
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] nums, int target) {
backtrack(nums, target, 0, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] nums, int target, int start,
int sum, List<Integer> path) {
if (sum == target) {
result.add(new ArrayList<>(path));
}
for (int i = start; i < nums.length; i++) {
if (sum + nums[i] <= target) {
path.add(nums[i]);
sum = sum + nums[i];
if (sum + nums[i] <= target) {
backtrack(nums, target, i, sum, path);
} else {
backtrack(nums, target, i + 1, sum, path);
}
path.remove(path.size() - 1);
sum = sum - nums[i];
}
}
}
}
// 2. DFS + backtrack
// 不用寫兩個 backtrack，當 nums[i] 不合時，會自動到 nums[i+1]
// 優化如下
//
// Time complexity: O(N^(T/M))
// Space complexity: O(N^(T/M))
//
// Dry run
// nums = [2,5,6,9], target = 9
// backtrack(9, 0, [])
// - backtrack(7, 0, [2])
// -- backtrack(5, 0, [2,2])
// --- backtrack(3, 0, [2,2,2])
// ---- backtrack(1, 0, [2,2,2,2]
// 2,2,2,2,2x, 5x, 6x, 9x
// --- 2,2,2,5x, 6x, 9x
// --- backtrack(0, 0, [2,2,5])
// 2,2, 6x, 9x
// -- backtrack(2, 0, [2,5])
// .....
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] nums, int target) {
backtrack(nums, target, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] nums, int remaining, int start, List<Integer> path) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < nums.length; i++) {
if (nums[i] > remaining) {
continue;
}
path.add(nums[i]);
backtrack(nums, remaining - nums[i], i, path);
path.remove(path.size() - 1);
}
}
}3. Combination Sum II
// 1. DFS + backtrack
// 題目希望避免有重複的結果，可以先 sort，每次開頭數字不能相同。
//
// 假設有 N 個 nums
// Time complexity: O(NlogN + (T/M)*2^N)
// 結果有幾種：每個數字只能選一次，選和不選: 2^N
// 每個結果都要 copy path: 每次 T/M
// Space complexity: O((T/M)*2^N)
// recursive: N
// result: (T/M)*2^N
//
// Dry run
// candidates = [9,2,2,4,6,1,5], target = 8
// sort: [1,2,2,4,5,6,9]
// [1] remaining: 7
// [1,2] r:5
// [1,2,2] r:3
// [1,2,4] r:2
// [1,2,6] -> v
// [1,2] x i > start
// [1,4] r:4
// ...
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backtrack(candidates, target, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] candidates, int remaining, int start, List<Integer> path) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] > remaining) {
break;
}
path.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i + 1, path);
path.remove(path.size() - 1);
}
}
}4. Permutations
// 1. DFS + backtrack
// 前面的題目都是照順序，選或不選，而這次是每次都有 n 個選擇，
// 因此要把 start 拿掉，每次都要 for loop 所有選擇
//
// 假設有 n 個 nums
// Time complexity: O(n*n!)
// -結果有幾種：n!
// -copy path: n
// Space complexity: O(n*n!)
// - recursive: O(n)
// - result: n*n!
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
backtrack(nums, new HashSet<>(), new ArrayList<>());
return result;
}
private void backtrack(int[] nums, Set<Integer> set, List<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
continue;
}
path.add(nums[i]);
set.add(nums[i]);
backtrack(nums, set, path);
path.remove(path.size() - 1);
set.remove(nums[i]);
}
}
}5. Subsets II
// 1.
// 題目不希望有 duplicate 的答案，因此可以先 sort，避免同一個 level 有相同的選擇
// 然後再下一層要從 i + 1 開始
//
// 假設 nums 有 n 個
// Time complexity: O(n*2^n)
// - sort: nlogn
// - 結果：2^n
// - path: n
// Space complexity: O(n*2^n)
// - recursive: n
// - result: n*2^n
//
// Dry run
// nums = [1,2,1]
// sort: [1,1,2]
// []
// [1]
// [1, 1]
// [1, 1, 2]
// [1, 2]
// [2]
class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(nums, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] nums, int start, List<Integer> path) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backtrack(nums, i + 1, path);
path.remove(path.size() - 1);
}
}
}6. Generate Parentheses
// 1. DFS + backtrack
// 題目希望產所有的 parenthese，一種是 "((()))" 拿去任意排列，但如果不是合法的就丟棄。
// 判別方式可以是最後才判別，但每次判別需要 O(n)
//
// Time complexity: O(n^2*(2n)!)
// - 結果: (2n)!
// - copy path: n
// - 判別是否是合法的: n
// Space complexity: O(n * (2n)!/n!n!)
// - recursive: n
// - 結果: n*Cn -> n * (2n)!/n!n!
// 2. DFS + backtrack
// 一種是每一次選擇有"("和")"兩種選擇
//
// Time complexity: O(n*(2n)!/n!n!)
// - 結果: Cn = (2n)!/n!n!
// - copy path: n
// Space complexity: O((2n)!/n!n!)
// - recursive: 2n
// - 結果: (2n)!/n!n!
//
// Dry run
// (
// ((
// (((
// ((()
// ((())
// ((()))
// (()())
// ...
class Solution {
private List<String> result = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtrack(0, 0, n, new StringBuilder());
return result;
}
private void backtrack(int left, int right, int n, StringBuilder path) {
if (left == n && right == n) {
result.add(path.toString());
return;
}
if (left < n) {
path.append("(");
backtrack(left + 1, right, n, path);
path.deleteCharAt(path.length() - 1);
}
if (right + 1 <= left) {
path.append(')');
backtrack(left, right + 1, n, path);
path.deleteCharAt(path.length() - 1);
}
}
}7. Word Search
// 1. DFS + backtrack
// 在 Trie 那邊的 Word SearchII 有多個 word，因此會把 word 建成一個 Trie tree，
// 在 DFS 和 backtrack 的過程中，把 2D-grid 走遍。
// 在這一題，只有一個 word，可以只用單純的 DFS + backtrack 走遍 2D-grid
//
// 假設 board 是 m*n, word 長 k
// Time complexity: O(m*n*3^k)
// Space complexity: O(k)
//
// Dry run
// board = ABCD
// SAAT
// ACAE
// word = "CAT"
// Ax
// Bx
// CAAx
// CATv
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (backtrack(board, i, j, 0, word)) {
return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, int r, int c, int start, String word) {
if (start == word.length()) {
return true;
}
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
return false;
}
if (board[r][c] == '#') {
return false;
}
char ch = board[r][c];
if (ch != word.charAt(start)) {
return false;
}
board[r][c] = '#';
boolean found = backtrack(board, r + 1, c, start + 1, word)
|| backtrack(board, r - 1, c, start + 1, word)
|| backtrack(board, r, c + 1, start + 1, word)
|| backtrack(board, r, c - 1, start + 1, word);
board[r][c] = ch;
return found;
}
}8. Palindrome Partitioning
// 1.
// s = "aab"
// 要將一個字串切成多份，並確保每個 substring 都是 Palindrome
// a choose 1~n, choose 1~n ...
// 每一層都要檢查是否是 palindrome
//
// 第一層有 1~n 可以選，有多少種組合 -> 可以想像成要在哪裡放加號，有n-1種選擇，2^(n-1)
// 3
// 1 1 1
// 1 2
// 2 1
// 3
//
// Time complexity: O(n^(2)*2^(n-1))
// 組合：2^(n-1)
// 檢查 palindrome: n
// copy: n
// Space complxity: O(n*2^(n-1))
// result: 2^(n-1)
// recursive: n
//
// Dry run
// s = "aab"
// a, a, b
// aa, b
class Solution {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> partition(String s) {
backtrack(s, 0, new ArrayList<>());
return result;
}
private void backtrack(String s, int start, List<String> path) {
if (start == s.length()) {
result.add(new ArrayList(path));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s.substring(start, i + 1))) {
path.add(s.substring(start, i + 1));
backtrack(s, i + 1, path);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s) {
if (s == null || s.equals("")) {
return false;
}
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}9. Letter Combinations of a Phone Number
// 1.
// digits = "34"
// 一連串的 digits 把所有可能的組合印出
// for loop digits, 再 for loop 該 digit 的可能選擇
//
// 假設有 n 個字母
// Time complexity: O(n*4^n)
// 組合: 4^n
// 每個組合: n
// Space complexity: O(n*4^n)
// recursive: n
// 組合: n*4^n
class Solution {
private List<String> result = new ArrayList<>();
private Map<Character, List<Character>> map = new HashMap<>();
public List<String> letterCombinations(String digits) {
map.put('0', List.of());
map.put('1', List.of());
map.put('2', List.of('a', 'b', 'c'));
map.put('3', List.of('d', 'e', 'f'));
map.put('4', List.of('g', 'h', 'i'));
map.put('5', List.of('j', 'k', 'l'));
map.put('6', List.of('m', 'n', 'o'));
map.put('7', List.of('p', 'q', 'r', 's'));
map.put('8', List.of('t', 'u', 'v'));
map.put('9', List.of('w', 'x', 'y', 'z'));
if (digits.isEmpty()) {
return result;
}
backtrack(digits, 0, new StringBuilder());
return result;
}
private void backtrack(String digits, int start, StringBuilder path) {
if (start == digits.length()) {
result.add(path.toString());
return;
}
List<Character> letters = map.get(digits.charAt(start));
for (char letter : letters) {
path.append(letter);
backtrack(digits, start + 1, path);
path.deleteCharAt(path.length() - 1);
}
}
}10. N-Queens
// 1.
// 題目要每一行放一個 queen，但垂直平行或是斜的都不能有其他 queen
// for (row) {
// check 上面和斜上不能有 queen
// back 1 .. n
// }
//
// 假設 matrix 是 n * n
// Time complexity: O(n*n!+S*n^2)
// - 組合: 每一個 row 有 n 個位置可選，下一個 row 有 n-1 個 -> n!
// - isVliad: n
// - 答案有 S 個，面積 n*n
// Space complexity: O(S*n^2)
// - board: n^2
// - recursive: n
// - 答案: S*n*n
class Solution {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] matrix = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = '.';
}
}
backtrack(matrix, 0, n);
return result;
}
private void backtrack(char[][] matrix, int row, int n) {
if (row == n) {
List<String> solution = new ArrayList<>();
for(int i = 0; i < n; i++) {
solution.add(new String(matrix[i]));
}
result.add(solution);
}
for (int i = 0; i < n; i++) {
if (isValid(matrix, row, i, n)) {
matrix[row][i] = 'Q';
backtrack(matrix, row + 1, n);
matrix[row][i] = '.';
}
}
}
private boolean isValid(char[][] matrix, int r, int c, int n) {
// check vertical
for (int i = 0; i < r; i++) {
if (matrix[i][c] == 'Q') {
return false;
}
}
// check left upper
int i = r - 1;
int j = c - 1;
while (i >= 0 && j >= 0) {
if (matrix[i][j] == 'Q') {
return false;
}
i--;
j--;
}
// check right upper
i = r - 1;
j = c + 1;
while (i >= 0 && j < n) {
if (matrix[i][j] == 'Q') {
return false;
}
i--;
j++;
}
return true;
}
}
