leetcode思路-回溯相关（46.全排列、78.子集、17.电话号码的字母组合）

46.全排列

给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

思路：

使用成员变量nums和res维护当前排列以及所有列举过的排列

固定前缀，递归地对后续元素进行排列组合，每生成一个完整的答案时就回溯返回到上一级

//存储当前排列 List<Integer> nums; //存储所有排列 List<List<Integer>> res; public List<List<Integer>> permute(int[] nums) { this.nums = new ArrayList<>(); this.res = new ArrayList<>(); //初始化nums for(int num:nums){ this.nums.add(num); } //固定第一位开始排列组合，也就是固定nums[0] DFS(0); return res; } //当前递归做的事情： //将当前位数的数字分别与其后置位每个数字交换一次，然后进到下一层递归，注意每次递归完后要进行回溯 void DFS(int x){ //如果当前固定的位数已经是倒数第二位，那么不需要再进行排列组合 // 因为后面只有一位数，没人跟它交换 if(x == nums.size() - 1){ res.add(new ArrayList<>(nums)); return; } for(int i = x;i < nums.size();i++){ swap(i,x); //将该固定的首位向右移动一位，达到进入下一层递归的效果 DFS(x + 1); //回溯 swap(i,x); } } void swap(int i,int x){ int temp = nums.get(i); nums.set(i,nums.get(x)); nums.set(x,temp); }

78.子集

给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

思路：

使用成员变量ans和path维护所有子集和当前路径

从第一个元素开始递归地进行选择，要么添加进当前路径、要么不添加，直到选择的次数与集合内元素数量相等（即一个子集构建完成）、将当前路径加入ans中。

注意，每个路径选择完成后都要进行回溯，保护每个路径构建过程独立不受干扰。

List<List<Integer>> ans; List<Integer> path; public List<List<Integer>> subsets(int[] nums) { this.ans = new ArrayList<>(); this.path = new ArrayList<>(); DFS(0,nums); return ans; } public void DFS(int i,int[] nums){ //全部选择完成，将当前路径添加到子集集合中 if(i == nums.length){ ans.add(new ArrayList<>(path)); return; } //如果不选择当前元素 DFS(i + 1,nums); //如果选择当前元素 path.add(nums[i]); DFS(i + 1,nums); //回溯 path.remove(path.size() - 1); }

17.电话号码的字母组合

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路：

使用成员变量ans维护所有可能字母组合

使用一个变量代表递归次数（也就是当前路径长度）

当前递归做的事情：

对当前传入的电话号码，选择一个其代表的字母（选择哪个字母由当前遍历的次数决定）添加到路径里，路径长度加一，进入下一层递归

结束递归条件：

路径长度满足传入电话号码数量

public final String[] MAP = new String[]{"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; List<String> ans; public List<String> letterCombinations(String digits) { ans = new ArrayList<>(); int n = digits.length(); if (n == 0) { return List.of(); } char[] path = new char[n]; DFS(0,digits.toCharArray(),path); return ans; } void DFS(int i,char[] digits,char[] path){ if(i == digits.length){ ans.add(new String(path)); return; } int n = digits[i] - '0'; for(char c:MAP[n].toCharArray()){ path[i] = c; DFS(i + 1,digits,path); } }