hot100之回溯上

全排列(046)

1. class Solution {
2.     List<List<Integer>> res = new ArrayList<>();
3.     public List<List<Integer>> permute(int[] nums) {
4.         int n = nums.length;
5.         List<Integer> path = new ArrayList<>(n);
6.         for (int num : nums){
7.             path.add(num);
8.         }
10.         backTrack(0, path, n);
11.         return res;
12.     }
14.     private void backTrack(int idx, List<Integer> path, int len){
15.         if (idx == len-1){
16.             res.add(new ArrayList(path));
17.             return;
18.         }
20.         for (int i = idx; i < len; i++){
21.             Collections.swap(path, idx, i);
22.             backTrack(idx+1, path, len);
23.             Collections.swap(path, idx, i);
24.         }
25.     }
26. }

复制代码

• 分析
  

根据排列组合, 我们可以得到 答案的数量为 nums.length()的阶乘
假设 n = nums.length =3
对于第一个数的选择有三种可能 ∗3
对于第二个数的选择有两种可能 ∗2(两个数未选)
对于第三个数的选择有一种可能 ∗1(一个数未选)
有以下关键代码

1. for (int i = idx; i < len; i++){
2.   Collections.swap(path, idx, i);
3.         backTrack(idx+1, path, len);
4.   Collections.swap(path, idx, i);
5. }

复制代码

子集(078)

1. class Solution {
2.     List<List<Integer>> res = new ArrayList<>();
3.     public List<List<Integer>> subsets(int[] nums) {
4.         int n = nums.length;
5.         List<Integer> path = new ArrayList<>();
6.         backTrace(0, path, nums, n);
7.         return res;
8.     }
10.     private void backTrace(int idx, List<Integer> path, int[] nums, int len){
11.         if (idx == len){
12.             res.add(new ArrayList(path));
13.             return;
14.         }
15.         path.add(nums[idx]);
16.         backTrace(idx+1, path, nums, len);
17.         path.remove(path.size()-1);
18.         backTrace(idx+1, path, nums, len);
19.     }
20. }

复制代码

• 分析
  

标准的背包问题, 选或不选
电话号码的字母组合(017)

1. class Solution {
2.     String[] mapping = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
3.     List<String> res = new ArrayList<>();
4.     public List<String> letterCombinations(String digits) {
5.         int n = digits.length();
6.         if (!digits.isEmpty()) backTrace(0, digits, new StringBuilder(), n);
7.         return res;
8.     }
10.     private void backTrace(int idx, String digits, StringBuilder builder, int len){
11.         if (idx == len){
12.             res.add(builder.toString());
13.             return;
14.         }
16.         char c = digits.charAt(idx);
17.         c -= '0';
18.         for (char d : mapping[c].toCharArray()){
19.             builder.append(d);
20.             backTrace(idx+1, digits, builder, len);
21.             builder.deleteCharAt(builder.length()-1);
22.         }
23.     }
24. }

复制代码

• 分析
  

标准简单回溯
组合总和(039)

1. class Solution {
2.     List<List<Integer>> res = new ArrayList<>();
3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
4.         Arrays.sort(candidates);
5.         List<Integer> path = new ArrayList<>();
6.         backTrace(0, target, path, candidates);
7.         return res;
8.     }
9.     private void backTrace(int idx, int target, List<Integer> path, int[] candidates){
10.         if (target == 0){
11.             res.add(new ArrayList(path));
12.             return;
13.         }
15.         if (idx == candidates.length || target < candidates[idx])  return;
17.         backTrace(idx+1, target, path, candidates);
18.         path.add(candidates[idx]);
19.         backTrace(idx, target - candidates[idx], path, candidates);
20.         path.remove(path.size()-1);
21.     }
22. }

复制代码

• 分析
  

我愿称他为原地背包, 也不知道有没有这种说法
括号生成(022)

1. class Solution {
2.     List<String> res = new ArrayList<>();
3.     public List<String> generateParenthesis(int n) {
4.         StringBuilder builder = new StringBuilder();
5.         backTrace(n, n, builder);
6.         return res;
7.     }
8.     private void backTrace(int lef, int rig, StringBuilder builder){
9.         if (lef > rig || lef < 0 || rig < 0)  return;
10.         if (lef == 0 && rig == 0){
11.             res.add(builder.toString());
12.             return;
13.         }
15.         backTrace(lef-1, rig, builder.append('('));
16.         builder.deleteCharAt(builder.length()-1);
17.         backTrace(lef, rig-1, builder.append(')'));
18.         builder.deleteCharAt(builder.length()-1);
19.     }
20. }

复制代码

• 分析
  

标准回溯 + 括号 →的限制条件

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！