题型一：排列、组合、子集相关问题
46. 全排列（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> permute(int[] nums
) {
boolean[] numsVisited
= new boolean[nums
.length
];
int[] result
= new int[nums
.length
];
fun(nums
, numsVisited
, result
, 0);
return ans
;
}
private void fun(int[] nums
, boolean[] numsVisited
, int[] result
, int c
) {
if (c
== nums
.length
) {
List
<Integer> temp
= new ArrayList<>();
for (int i
= 0; i
< result
.length
; i
++) {
temp
.add(result
[i
]);
}
ans
.add(temp
);
return;
}
for (int i
= 0; i
< result
.length
; i
++) {
if (!numsVisited
[i
]) {
numsVisited
[i
] = true;
result
[c
] = nums
[i
];
fun(nums
, numsVisited
, result
, ++c
);
c
--;
numsVisited
[i
] = false;
}
}
return;
}
}
不需要剪枝，直接回溯
47. 全排列 II（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> permuteUnique(int[] nums
) {
Arrays
.sort(nums
);
fun(new LinkedList<>(), new boolean[nums
.length
], nums
);
return ans
;
}
public void fun(LinkedList
<Integer> result
, boolean[] used
, int[] nums
) {
if (nums
.length
== result
.size()) {
List
<Integer> temp
= new ArrayList<>();
temp
.addAll(result
);
ans
.add(temp
);
return;
}
for (int i
= 0; i
< nums
.length
; i
++) {
if (used
[i
])
continue;
if (i
> 0 && nums
[i
] == nums
[i
- 1] && !used
[i
-1])
continue;
used
[i
] = true;
result
.add(nums
[i
]);
fun(result
, used
, nums
);
result
.removeLast();
used
[i
] = false;
}
}
}
平级剪枝，用!used[i]表示同级，修正相同元素
39. 组合总和（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> combinationSum(int[] candidates
, int target
) {
fun(candidates
, 0, target
, new LinkedList<>(), 0);
return ans
;
}
public void fun(int[] candidates
, int currennt
, int target
, LinkedList
<Integer> result
, int index
) {
if (currennt
== target
) {
List
<Integer> temp
= new ArrayList();
temp
.addAll(result
);
ans
.add(temp
);
return;
}
for (int i
= index
; i
< candidates
.length
; i
++) {
if (currennt
> target
) {
continue;
}
currennt
+= candidates
[i
];
result
.add(candidates
[i
]);
fun(candidates
, currennt
, target
, result
, i
);
result
.removeLast();
currennt
-= candidates
[i
];
}
}
}
通过传入index区分组合，用index来截断数组，分别用数组的各个组成部分算。
40. 组合总和 II（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> combinationSum2(int[] candidates
, int target
) {
Arrays
.sort(candidates
);
fun(new boolean[candidates
.length
], candidates
, target
, 0, new LinkedList<>(), 0);
return ans
;
}
public void fun(boolean[] used
, int[] candidates
, int target
, int current
, LinkedList
<Integer> result
, int index
) {
if (target
== current
) {
List
<Integer> temp
= new ArrayList<>();
temp
.addAll(result
);
ans
.add(temp
);
return;
}
for (int i
= index
; i
< candidates
.length
; i
++) {
if (used
[i
]) {
continue;
}
if (current
> target
) {
continue;
}
if (i
> index
&& candidates
[i
] == candidates
[i
- 1]) {
continue;
}
result
.addLast(candidates
[i
]);
used
[i
] = true;
current
+=candidates
[i
];
fun(used
, candidates
, target
, current
, result
, i
+ 1);
result
.removeLast();
used
[i
] = false;
current
-=candidates
[i
];
}
}
}
index变为+1，用和排列2的方式
77. 组合（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> combine(int n
, int k
) {
fun(0, k
, new LinkedList<>(), n
, new boolean[n
+1], 1);
return ans
;
}
public void fun(int current
, int k
, LinkedList
<Integer> result
, int n
, boolean[] used
, int index
) {
if (current
== k
) {
List
<Integer> temp
= new ArrayList<>();
temp
.addAll(result
);
ans
.add(temp
);
return;
}
for (int i
= index
; i
<= n
; i
++) {
if (used
[i
]) {
continue;
}
result
.add(i
);
current
++;
used
[i
] = true;
fun(current
, k
, result
, n
, used
, i
+1);
used
[i
] = false;
current
--;
result
.removeLast();
}
}
}
组合特有index，+1表示不重复使用
78. 子集（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> subsets(int[] nums
) {
fun(new LinkedList<>(), nums
, new boolean[nums
.length
], 0);
return ans
;
}
public void fun(LinkedList
<Integer> result
, int[] nums
, boolean[] used
, int index
) {
List
<Integer> temp
= new ArrayList<>();
temp
.addAll(result
);
ans
.add(temp
);
for (int i
= index
; i
< nums
.length
; i
++) {
result
.add(nums
[i
]);
fun(result
, nums
, used
, i
+ 1);
result
.removeLast();
}
}
}
子集问题是全部加进来，因为子集是一个元素用一次，所以index + 1
90. 子集 II（中等）
class Solution {
List
<List
<Integer>> ans
= new ArrayList<>();
public List
<List
<Integer>> subsetsWithDup(int[] nums
) {
Arrays
.sort(nums
);
fun(nums
, new LinkedList<>(), 0);
return ans
;
}
public void fun(int[] nums
, LinkedList
<Integer> result
, int index
) {
List
<Integer> temp
= new ArrayList<>();
temp
.addAll(result
);
ans
.add(temp
);
for (int i
= index
; i
< nums
.length
; i
++) {
if (i
> index
&& nums
[i
] == nums
[i
- 1]) {
continue;
}
result
.add(nums
[i
]);
fun(nums
, result
, i
+1);
result
.removeLast();
}
}
}
防止重复，用排序 + nums[i] == nums[i - 1]
60. 第 k 个排列（中等）
class Solution {
String ans
;
int current
= 0;
public String
getPermutation(int n
, int k
) {
int[] nums
= new int[n
];
for (int i
= 1; i
< n
+ 1; i
++) {
nums
[i
- 1] = i
;
}
fun(nums
, new boolean[n
], k
, new LinkedList<>());
return ans
;
}
public void fun(int[] nums
, boolean[] used
, int k
, LinkedList
<Integer> result
) {
if (current
== k
) {
return;
}
if (result
.size() == nums
.length
) {
current
++;
String ans
= "";
if (current
== k
) {
for (int i
= 0; i
< result
.size(); i
++) {
ans
+=result
.get(i
);
}
this.ans
= ans
;
}
}
for (int i
= 0; i
< nums
.length
; i
++) {
if (used
[i
]) {
continue;
}
result
.add(nums
[i
]);
used
[i
] = true;
fun(nums
, used
, k
, result
);
used
[i
] = false;
result
.removeLast();
}
}
}
排序，current++
93. 复原 IP 地址（中等）后续更新
总结
整体分为三个类型：排列，组合，子集
排列
完全回溯
组合
index来是实现组合，+1表示不重复
子集
所有的都加入ans
算法
i > index && candidates[i] == candidates[i - 1] 解决重复问题传入index 组合可重复使用传入index + 1 组合使用不可重复
题型二：Flood Fill
733. 图像渲染（Flood Fill，中等）
class Solution {
public int[][] floodFill(int[][] image
, int sr
, int sc
, int newColor
) {
if (image
[sr
][sc
] == newColor
) {
return image
;
}
fun(image
, sr
, sc
, image
[sr
][sc
], newColor
);
return image
;
}
public void fun(int[][] image
, int x
, int y
, int color
, int newColor
) {
if (color
== image
[x
][y
]) {
image
[x
][y
] = newColor
;
if (x
> 0) {
fun(image
, x
-1, y
, color
, newColor
);
}
if (y
> 0) {
fun(image
, x
, y
-1, color
, newColor
);
}
if (x
< image
.length
- 1) {
fun(image
, x
+1, y
, color
, newColor
);
}
if (y
< image
[0].length
- 1) {
fun(image
, x
, y
+1, color
, newColor
);
}
}
}
}
200. 岛屿数量（中等）
class Solution {
int ans
= 0;
public int numIslands(char[][] grid
) {
if (grid
.length
== 0) {
return 0;
}
boolean[][] visited
= new boolean[grid
.length
][grid
[0].length
];
fun(grid
, visited
);
return ans
;
}
public void fun(char[][] grid
, boolean[][] visited
) {
int m
= visited
.length
;
int n
= visited
[0].length
;
for (int i
= 0; i
< m
; i
++) {
for (int j
= 0; j
< n
; j
++) {
if (!visited
[i
][j
]) {
fun2(grid
, visited
, i
, j
, true);
}
}
}
}
public void fun2(char[][] grid
, boolean[][] visited
, int x
, int y
, boolean newFlag
) {
if (visited
[x
][y
]) {
return;
}
visited
[x
][y
] = true;
if (grid
[x
][y
] == '1') {
if (newFlag
)
ans
++;
if (x
> 0) {
fun2(grid
, visited
, x
- 1, y
, false);
}
if (y
> 0) {
fun2(grid
, visited
, x
, y
- 1, false);
}
if (x
< visited
.length
- 1) {
fun2(grid
, visited
, x
+ 1, y
, false);
}
if (y
< visited
[0].length
- 1) {
fun2(grid
, visited
, x
, y
+ 1, false);
}
}
}
}
130. 被围绕的区域（中等）
class Solution {
public void solve(char[][] board
) {
if (board
.length
== 0) {
return;
}
int m
= board
.length
;
int n
= board
[0].length
;
boolean[][] visited
= new boolean[m
][n
];
for (int i
= 0; i
< m
; i
++) {
for (int j
= 0; j
< n
; j
++) {
boolean isEdge
= i
== 0 || j
== 0 || i
== m
- 1|| j
== n
- 1;
if (isEdge
&& board
[i
][j
] == 'O') {
fun(board
, visited
, i
, j
);
}
}
}
for (int i
= 0; i
< m
; i
++) {
for (int j
= 0; j
< n
; j
++) {
if (board
[i
][j
] == 'O') {
board
[i
][j
] = 'X';
}
if (board
[i
][j
] == '#') {
board
[i
][j
] = 'O';
}
}
}
}
public void fun(char[][] board
, boolean[][] visited
, int x
, int y
) {
if (visited
[x
][y
]) {
return;
}
visited
[x
][y
] = true;
if (board
[x
][y
] == 'O') {
board
[x
][y
] = '#';
if (x
> 0) {
fun(board
, visited
, x
- 1, y
);
}
if (y
> 0) {
fun(board
, visited
, x
, y
- 1);
}
if (x
< visited
.length
- 1) {
fun(board
, visited
, x
+ 1, y
);
}
if (y
< visited
[0].length
- 1) {
fun(board
, visited
, x
, y
+ 1);
}
}
}
}
79. 单词搜索（中等）
class Solution {
public boolean exist(char[][] board
, String word
) {
int m
= board
.length
;
int n
= board
[0].length
;
boolean[][] visited
= new boolean[m
][n
];
for (int i
= 0; i
< m
; i
++) {
for (int j
= 0; j
< n
; j
++) {
if (board
[i
][j
] == word
.charAt(0)) {
if(fun(board
, word
, 0, visited
, i
, j
)) {
return true;
}
}
}
}
return false;
}
public boolean fun(char[][] board
, String word
, int index
, boolean[][] visited
, int x
, int y
) {
if (!visited
[x
][y
] && board
[x
][y
] == word
.charAt(index
)) {
visited
[x
][y
] = true;
boolean a
= false, b
= false, c
= false, d
= false;
if (index
== word
.length() - 1) {
return true;
}
if (x
> 0) {
a
= fun(board
, word
, index
+ 1, visited
, x
- 1, y
);
if (a
) {
return a
;
}
}
if (y
> 0) {
b
= fun(board
, word
, index
+ 1, visited
, x
, y
- 1);
if (b
) {
return b
;
}
}
if (x
< board
.length
- 1) {
c
= fun(board
, word
, index
+ 1, visited
, x
+ 1, y
);
if (c
) {
return c
;
}
}
if (y
< board
[0].length
- 1) {
d
= fun(board
, word
, index
+ 1, visited
, x
, y
+ 1);
if (d
) {
return d
;
}
}
visited
[x
][y
] = false;
}
return false;
}
}
题型三：字符串中的回溯问题
17. 电话号码的字母组合（中等）
class Solution {
private Map
<Character, String> map
= new HashMap<>();
public List
<String> letterCombinations(String digits
) {
if ("".equals(digits
)) {
return new ArrayList<>();
}
map
.put('2', "abc");
map
.put('3', "def");
map
.put('4', "ghi");
map
.put('5', "jkl");
map
.put('6', "mno");
map
.put('7', "pqrs");
map
.put('8', "tuv");
map
.put('9', "wxyz");
List
<String> result
= new ArrayList<>();
fun(digits
, 0, new StringBuilder(), result
);
return result
;
}
public void fun(String digits
, int index
, StringBuilder sb
, List
<String> result
) {
if (index
== digits
.length()) {
result
.add(sb
.toString());
} else {
char c
= digits
.charAt(index
);
String cs
= map
.get(c
);
for (int i
= 0; i
< cs
.length(); i
++) {
sb
.append(cs
.charAt(i
));
fun(digits
, index
+ 1, sb
, result
);
sb
.deleteCharAt(sb
.length() - 1);
}
}
}
}
784. 字母大小写全排列（中等）
class Solution {
public List
<String> letterCasePermutation(String S
) {
List
<String> result
= new ArrayList<>();
fun(result
, S
, 0);
return result
;
}
public void fun(List
<String> result
, String s
, int index
) {
result
.add(s
);
for (int i
= index
; i
< s
.length(); i
++) {
char c
= s
.charAt(i
);
if (c
>= '0' && c
<= '9') {
continue;
}
String t
;
if (c
>= 'a') {
t
= toUp(s
, i
);
} else {
t
= toDown(s
, i
);
}
fun(result
, t
, i
+ 1);
}
}
private String
toUp(String s
, int index
) {
StringBuilder sb
= new StringBuilder();
for (int i
= 0; i
< s
.length(); i
++) {
if (i
== index
) {
sb
.append(Character
.toUpperCase(s
.charAt(i
)));
} else {
sb
.append(s
.charAt(i
));
}
}
return sb
.toString();
}
private String
toDown(String s
, int index
) {
StringBuilder sb
= new StringBuilder();
for (int i
= 0; i
< s
.length(); i
++) {
if (i
== index
) {
sb
.append(Character
.toLowerCase(s
.charAt(i
)));
} else {
sb
.append(s
.charAt(i
));
}
}
return sb
.toString();
}
}
22. 括号生成（中等）
class Solution {
public List
<String> generateParenthesis(int n
) {
List
<String> result
= new ArrayList<>();
fun(result
, n
, n
, new StringBuilder());
return result
;
}
public void fun(List
<String> result
, int left
, int right
, StringBuilder sb
) {
if (left
== 0 && right
== 0) {
result
.add(sb
.toString());
}
if (left
> 0) {
sb
.append("(");
fun(result
, left
- 1, right
, sb
);
sb
.deleteCharAt(sb
.length() - 1);
}
if (right
> left
) {
sb
.append(")");
fun(result
, left
, right
- 1, sb
);
sb
.deleteCharAt(sb
.length() - 1);
}
}
}
