hot100之回溯上

辖瑁地 发表于 2025-9-25 11:03:56

全排列(046)

class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
   int n = nums.length;
   List<Integer> path = new ArrayList<>(n);
   for (int num : nums){
         path.add(num);
   }

   backTrack(0, path, n);
   return res;
}

private void backTrack(int idx, List<Integer> path, int len){
   if (idx == len-1){
         res.add(new ArrayList(path));
         return;
   }

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

[*]分析
根据排列组合, 我们可以得到答案的数量为 nums.length()的阶乘
假设 n = nums.length =3
对于第一个数的选择有三种可能 ∗3
对于第二个数的选择有两种可能 ∗2(两个数未选)
对于第三个数的选择有一种可能 ∗1(一个数未选)
有以下关键代码
for (int i = idx; i < len; i++){
Collections.swap(path, idx, i);
backTrack(idx+1, path, len);
Collections.swap(path, idx, i);
}子集(078)

class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
   int n = nums.length;
   List<Integer> path = new ArrayList<>();
   backTrace(0, path, nums, n);
   return res;
}

private void backTrace(int idx, List<Integer> path, int[] nums, int len){
   if (idx == len){
         res.add(new ArrayList(path));
         return;
   }
   path.add(nums);
   backTrace(idx+1, path, nums, len);
   path.remove(path.size()-1);
   backTrace(idx+1, path, nums, len);
}
}

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

class Solution {
String[] mapping = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
   int n = digits.length();
   if (!digits.isEmpty()) backTrace(0, digits, new StringBuilder(), n);
   return res;
}

private void backTrace(int idx, String digits, StringBuilder builder, int len){
   if (idx == len){
         res.add(builder.toString());
         return;
   }

   char c = digits.charAt(idx);
   c -= '0';
   for (char d : mapping.toCharArray()){
         builder.append(d);
         backTrace(idx+1, digits, builder, len);
         builder.deleteCharAt(builder.length()-1);
   }
}
}

[*]分析
标准简单回溯
组合总和(039)

class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
   Arrays.sort(candidates);
   List<Integer> path = new ArrayList<>();
   backTrace(0, target, path, candidates);
   return res;
}
private void backTrace(int idx, int target, List<Integer> path, int[] candidates){
   if (target == 0){
         res.add(new ArrayList(path));
         return;
   }

   if (idx == candidates.length || target < candidates)return;

   backTrace(idx+1, target, path, candidates);
   path.add(candidates);
   backTrace(idx, target - candidates, path, candidates);
   path.remove(path.size()-1);
}
}

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

class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
   StringBuilder builder = new StringBuilder();
   backTrace(n, n, builder);
   return res;
}
private void backTrace(int lef, int rig, StringBuilder builder){
   if (lef > rig || lef < 0 || rig < 0)return;
   if (lef == 0 && rig == 0){
         res.add(builder.toString());
         return;
   }

   backTrace(lef-1, rig, builder.append('('));
   builder.deleteCharAt(builder.length()-1);
   backTrace(lef, rig-1, builder.append(')'));
   builder.deleteCharAt(builder.length()-1);
}
}

[*]分析
标准回溯 + 括号 →的限制条件

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

骛扼铮 发表于 20 小时前

谢谢楼主提供！

页: [1]

程序园's Archiver

hot100之回溯上