Hot100

Hot100

回溯

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

  class Solution {
      List<List<Integer>>res;
      int len=0;
      public List<List<Integer>> permute(int[] nums) {
          this.res=new LinkedList<>();
          this.len=nums.length;
          dfs(nums,new LinkedList<>(),new boolean[len]);
          return res;
      }
      public void dfs(int[] nums,LinkedList path,boolean[]p){
          if(path.size()==len){
              res.add(new LinkedList<>(path));
              return;
          }
          for(int i=0;i<len;i++){
              if(p[i]){
                  continue;
              }
              p[i]=true;
              path.add(nums[i]);
              dfs(nums,path,p);
              p[i]=false;
              path.remove(path.size()-1);
          }
      }
  }
  

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

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

  class Solution {
      List<List<Integer>>res=new LinkedList<>();
      LinkedList<Integer>track=new LinkedList<>();
      public List<List<Integer>> subsets(int[] nums) {
          backtracking(nums,0);
          return res;
      }
      public void backtracking(int[] nums,int start){
          res.add(new LinkedList<>(track));
          for(int i=start;i<nums.length;i++){
              track.addLast(nums[i]);
              backtracking(nums,i+1);
              track.removeLast();
          }
      }
  }
  

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

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

  class Solution {
      public List<String> letterCombinations(String digits) {
          if(digits.length()<1){
              return new LinkedList<String>();
          }
          List<String>res=new LinkedList<>();
          res.add("");
          HashMap<Character,String>map=new HashMap<>();
          map.put('2',"abc");
          map.put('3',"def");
          map.put('4',"ghi");
          map.put('5',"jkl");
          map.put('6',"mno");
          map.put('7',"pqrs");
          map.put('8',"tuv");
          map.put('9',"wxyz");
          for(Character c1:digits.toCharArray()){//取每个数字
              LinkedList<String>ne=new LinkedList<>();
              for(Character c2:map.get(c1).toCharArray()){//取每个数字的对应值
                  for(String s1:res){//res存上一次组成的字符串，把新增加入存量字符串用ne
                     StringBuffer s2=new StringBuffer(s1);    
                      s2.append(c2);
                      String str=s2.toString();
                      ne.add(str);
                  }
              }
              res=ne;//res指向新更新的值地址
          }
          return res;
      }
  }
  

  递归解法

  class Solution {
      private static final String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  
      private final List<String> ans = new ArrayList<>();
      private char[] digits;
      private char[] path;
  
      public List<String> letterCombinations(String digits) {
          int n = digits.length();
          if (n == 0) {
              return new ArrayList<>();
          }
          this.digits = digits.toCharArray();
          path = new char[n]; // 存入一次完整路径字符串
          dfs(0);
          return ans;
      }
  
      private void dfs(int i) {
          if (i == digits.length) {
              ans.add(new String(path));
              return;
          }
          for (char c : map[digits[i] - '0'].toCharArray()) {//按每个数字所针对字符数弄分支
              path[i] = c; // 直接覆盖
              dfs(i + 1);
          }
      }
  }
  

• 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

  candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的

  class Solution {
      List<List<Integer>>res=new LinkedList<>();
      LinkedList<Integer>track=new LinkedList<>();
      int trackSum=0;
      public List<List<Integer>> combinationSum(int[] candidates, int target) {
          backtrack(candidates,target,0);
          return res;
      }
      void backtrack(int[] candidates,int target,int start){
          if(trackSum==target){
              res.add(new LinkedList<>(track));
              return;
          }
          if(trackSum>target){
              return;
          }
          for(int i=start;i<candidates.length;i++){
              trackSum+=candidates[i];
              track.addLast(candidates[i]);
              backtrack(candidates,target,i);
              trackSum-=candidates[i];
              track.removeLast();
          }
      }
  }