46.全排列给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。思路使用成员变量nums和res维护当前排列以及所有列举过的排列固定前缀递归地对后续元素进行排列组合每生成一个完整的答案时就回溯返回到上一级//存储当前排列 ListInteger nums; //存储所有排列 ListListInteger res; public ListListInteger 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中。注意每个路径选择完成后都要进行回溯保护每个路径构建过程独立不受干扰。ListListInteger ans; ListInteger path; public ListListInteger 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}; ListString ans; public ListString 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); } }
