Backtracking
Adapted from programmercarl.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
int n = nums.length;
if (n == 0) {
return result;
}
used = new boolean[n];
helper(nums);
return result;
}
private void helper(int[] nums) {
int n = nums.length;
if (path.size() == n) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < n; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
helper(nums);
path.removeLast();
used[i] = false;
}
}
}
|
Remarks:
- Backtracking is a classic realization of DFS
- TC: $O(n\times n!)$
- Use global variables,
path to save the current combination, and result to save all combinations.
- This is a classic backtracking problem. Template for backtracking:
1
2
3
4
5
6
7
8
9
10
| void backTracking(params) {
...
if (endCondition) {
saveResult();
return;
}
...
backTracking(params)
...
}
|