组合

  • 法1 dfs :::warning 剪枝：对搜索起点的上界进行剪枝，剩下的需要加入集合的数字数量 > 剩下的可以被加入集合的数字数量 ，就不用向下遍历了。
    for (int i = cur; i <= (n - (k - path.size()) + 1); i++) ::: 1599488203-TzmCXb-image.png

    1. class Solution {
    3.   List<List<Integer>> res = new LinkedList();
    5.   List<Integer> path = new LinkedList();
    7.   public List<List<Integer>> combine(int n, int k) {
    8.       if (n < k) {
    9.           return res;
    10.       }
    11.       dfs(1, n, k);
    12.       return res;
    13.   }
    14.   void dfs(int cur, int n, int k) {
    15.       if (path.size() == k) {
    16.           res.add(new LinkedList(path));
    17.           return;
    18.       }
    19.       //剪枝
    20.       //for (int i = cur; i <= (n - (k - path.size()) + 1); i++) {
    21.       for (int i = cur; i <= n; i++) {
    22.           path.add(i);
    23.           dfs(i + 1, n, k);
    24.           path.remove(path.size() - 1);
    25.       }
    26.   }
    27. }

  • 法2 选或不选

回溯 - 图2

  1. class Solution {
  3.     List<List<Integer>> res = new LinkedList();
  5.     List<Integer> path = new LinkedList();
  7.     public List<List<Integer>> combine(int n, int k) {
  8.         if (n < k) {
  9.             return res;
  10.         }
  11.         dfs(1, n, k);
  12.         return res;
  13.     }
  15.     void dfs(int cur, int n, int k) {
  16.         if (k == 0) {
  17.             res.add(new LinkedList(path));
  18.             return;
  19.         }
  20.         //剪枝 同上
  21.         if (n - k + 1  < cur) {
  22.             return;
  23.         }
  24.         dfs(cur + 1, n, k);
  25.         path.add(cur);
  26.         dfs(cur + 1, n, k - 1);
  27.         path.remove(path.size() - 1);
  28.     }
  29. }

组合总和 III

  • 法1 选或不选

    class Solution {

  List<List<Integer>> res = new LinkedList();

  List<Integer> path = new LinkedList();

  public List<List<Integer>> combinationSum3(int k, int n) {
      dfs(1, k, 0, n);
      return res;
  }

  void dfs (int cur, int k, int sum, int target) {
      if (sum >= target) {
          if (sum == target && k == 0) {
              res.add(new LinkedList(path));
          }
          return;
      }
      if (k == 0 || cur > 9) {
          return;
      }
      //不选cur
      dfs(cur + 1, k, sum, target);
      //选cur
      path.add(cur);
      dfs(cur + 1, k - 1, sum + cur, target);
      path.remove(path.size() - 1);
  }
}

  • 法2 dfs 回溯 :::warning 剪枝：思路同组合
    i <= 9 - (k - path.size()) + 1 :::

    class Solution {

  List<List<Integer>> res = new LinkedList();

  List<Integer> path = new LinkedList();

  public List<List<Integer>> combinationSum3(int k, int n) {
      dfs(1, k, 0, n);
      return res;
  }

  void dfs (int cur, int k, int sum, int target) {
      if (path.size() > k) {
          return;
      }
      if (sum >= target) {
          if (sum == target && k == path.size()) {
              res.add(new LinkedList(path));
          }
          return;
      }
      for (int i = cur; i <= 9 - (k - path.size()) + 1; i++) {
          path.add(i);
          dfs(i + 1, k, sum + i, target);
          path.remove(path.size() - 1);
      }
  }
}

    组合总和

  • 法1 选或不选 :::warning 剪枝：对 candidates 数组排序，当前和大于 target 或者 当前和+下一个元素值的和大于 target，就不用进入下一循环。
    sum > target | | sum + candidates[index] > target :::

    class Solution {

  List<List<Integer>> res = new LinkedList();

  List<Integer> path = new LinkedList(); 

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
      //减枝2
      Arrays.sort(candidates);
      dfs(candidates, 0, 0, target);
      return res;
  }

  void dfs(int[] candidates, int index, int sum, int target){
      //减枝1
      if (sum > target || index >= candidates.length) {
          return;
      }
      if (sum == target) {
          res.add(new LinkedList(path));
          return;
      }
      //减枝2
      if (sum + candidates[index] > target) {
          return;
      }
      //不选 candidates[index]
      dfs(candidates, index + 1, sum , target);
      //选 candidates[index]
      path.add(candidates[index]);
      dfs(candidates, index, sum + candidates[index], target);
      path.remove(path.size() - 1);

  }
}

  • 法2 dfs 回溯 :::warning 剪枝：思路同上 :::

    class Solution {

  List<List<Integer>> res = new LinkedList();

  List<Integer> path = new LinkedList(); 

  public List<List<Integer>> combinationSum(int[] candidates, int target) {
      Arrays.sort(candidates);
      dfs(candidates, 0, 0, target);
      return res;
  }

  void dfs(int[] candidates, int index, int sum, int target){
      if (sum == target) {
          res.add(new LinkedList(path));
          return;
      }
      for (int i = index; i < candidates.length; i++) {
          //剪枝
          if (sum + candidates[i] > target) {
              break;
          }
          path.add(candidates[i]);
          dfs(candidates, i, sum + candidates[i], target);
          path.remove(path.size() - 1);
      }
  }
}

    组合总和 II

  • 法1 选或不选 :::warning 去除重复：数组排序后，对于相邻重复的元素就不能选择 :::

    class Solution {

  List<List<Integer>> res = new LinkedList();

  List<Integer> path = new LinkedList();

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      dfs(candidates, 0, 0, target);
      return res;
  }

  void dfs(int[] candidates, int index, int sum, int target) {
      if (sum == target) {
          res.add(new LinkedList(path));
          return;
      }
      if (index >= candidates.length || sum > target) {
          return;
      }
      //去除重复-不选
      int newIndex = index + 1;
      while (newIndex < candidates.length && candidates[newIndex] == candidates[newIndex - 1]) {
          newIndex++;
      }
      //不选
      dfs(candidates, newIndex, sum, target);
      //选
      path.add(candidates[index]);
      dfs(candidates, index + 1, sum + candidates[index], target);
      path.remove(path.size() - 1);
  }
}

  • 法2 dfs 回溯 :::warning 去除重复：先排序，for 循环中有相邻相等元素就continue。
    剪枝：遇到 sum > target 就直接 break，即终止同层的递归树。 :::

    class Solution {

  List<List<Integer>> res = new LinkedList();

  List<Integer> path = new LinkedList();

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      dfs(candidates, 0, 0, target);
      return res;
  }

  void dfs(int[] candidates, int index, int sum, int target) {
      if (sum == target) {
          res.add(new LinkedList(path));
          return;
      }
      for (int i = index; i < candidates.length; i++) {
          if (i > index && candidates[i] == candidates[i - 1]) {
              continue;
          }
          if (sum > target) {
              break;
          }
          path.add(candidates[i]);
          dfs(candidates, i + 1, sum + candidates[i], target);
          path.remove(path.size() - 1);
      } 
  }
}

    复原 IP 地址

  • 法1 选或不选 :::warning 三种情况：0~9，10~99，100~ 255
    后两种情况去除第一个字符为 0 的情况，即
    if (s.charAt(index) == ‘0’) return; :::

    class Solution {

  List<String> res = new LinkedList();

  List<String> path = new LinkedList();

  public List<String> restoreIpAddresses(String s) {
      if (s == null || s.length() <= 0 || s.length() > 12) {
          return res;
      }
      dfs(0, s);
      return res;
  }

  void dfs (int index, String s) {
      if (index == s.length() && path.size() == 4) {
          String tmp = "";
          for (String ip : path) {
              tmp += (ip + ".");
          }
          res.add(tmp.substring(0, tmp.length() - 1));
          return;
      }
      if (index >= s.length() || path.size() > 4) {
          return;
      }
      //0 - 9
      if (s.charAt(index) >= '0' || s.charAt(index) <= '9') {
          path.add(String.valueOf(s.charAt(index)));
          dfs(index + 1, s);
          path.remove(path.size() - 1);
      }
      //10 - 99
      if (index <= s.length() - 2) {
          //01-09 不满足要求 直接 return
          if (s.charAt(index) == '0') {
              return;
          }
          path.add(s.substring(index, index + 2));
          dfs(index + 2, s);
          path.remove(path.size() - 1);
      }
      //100 - 255
      if (index <= s.length() - 3) {
          //001-099 不满足要求 直接 return
          if (s.charAt(index) == '0') {
              return;
          }
          int ip = Integer.parseInt(s.substring(index, index + 3));
          if (ip >= 100 && ip <= 255) {
              path.add(s.substring(index, index + 3));
              dfs(index + 3, s);
              path.remove(path.size() - 1);
          }
      } 
  }
}

  • 法2 dfs 回溯

回溯 - 图3 :::warning 按照长度1，2，3 dfs，注意回溯条件。 :::

class Solution {

    List<String> res = new LinkedList();

    List<String> path = new LinkedList();

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() <= 0 || s.length() > 12) {
            return res;
        }
        dfs(0, s);
        return res;
    }

    void dfs (int index, String s) {
        if (index == s.length() && path.size() == 4) {
            String tmp = "";
            for (String ip : path) {
                tmp += (ip + ".");
            }
            res.add(tmp.substring(0, tmp.length() - 1));
            return;
        }
        if (index >= s.length() || path.size() > 4) {
            return;
        }
        for (int len = 1; len < 4; len++) {
            if (index + len - 1 >= s.length()) {
                return;
            }
            //首字符为 0 的情况 直接 return
            if (len != 1 && s.charAt(index) == '0') {
                return;
            }
            String ip = s.substring(index, index + len);
            //截取的字符串长度为3时，大小不能超过255
            if(len == 3 && Integer.parseInt(ip)>255){
                return;
            }
            path.add(ip);
            dfs(index + len, s);
            path.remove(path.size() - 1);
        }
    }
}

子集

  • 法1 选或不选 :::warning 递归树到达树的底部就添加进结果集 即
    if (index == nums.length) :::

    class Solution {

  List<List<Integer>> res = new ArrayList();

  List<Integer> path = new ArrayList();

  public List<List<Integer>> subsets(int[] nums) {
      dfs(0, nums);
      return res;
  }

  void dfs(int index, int[] nums) {
      if (index == nums.length) {
          res.add(new ArrayList(path));
          return;
      }
      //不选 nums[index]
      dfs(index + 1, nums);
      //选 nums[index]
      path.add(nums[index]);
      dfs(index + 1, nums);
      path.remove(path.size() - 1);
  }
}

  • 法2 dfs 回溯

    class Solution {

  List<List<Integer>> res = new ArrayList();

  List<Integer> path = new ArrayList();

  public List<List<Integer>> subsets(int[] nums) {
      dfs(0, nums);
      return res;
  }

  void dfs(int index, int[] nums) {
      res.add(new ArrayList(path));
      for (int i = index; i < nums.length; i++) {
          path.add(nums[i]);
          dfs(i + 1, nums);
          path.remove(path.size() - 1);
      }
  }
}

    递增子序列

  • 法1 选或不选 :::warning 去重见 解析 :::

    class Solution {

  List<List<Integer>> res = new ArrayList();

  List<Integer> path = new ArrayList();

  public List<List<Integer>> findSubsequences(int[] nums) {
      dfs(0, nums);
      return res;
  }

  void dfs(int index, int[] nums) {
      if (index == nums.length) {
          if (path.size() > 1) {
              res.add(new ArrayList(path));
          }   
          return;
      }
      //不选 nums[index]
      if (path.size() == 0 || path.get(path.size() - 1) != nums[index]) {
          dfs(index + 1, nums);
      }
      //选 nums[index]
      if (path.size() == 0 || path.get(path.size() - 1) <= nums[index]) {
          path.add(nums[index]);
          dfs(index + 1, nums);
          path.remove(path.size() - 1);
      }
  }
}

  • 法2 dfs 回溯

回溯 - 图4 :::warning 同层用 set 去除重复 :::

class Solution {

    List<List<Integer>> res = new ArrayList();

    List<Integer> path = new ArrayList();

    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(0, nums);
        return res;
    }

    void dfs(int index, int[] nums) {
        if (path.size() > 1) {
            res.add(new ArrayList(path));
        }
        Set<Integer> set = new HashSet();
        for (int i = index; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                continue;
            }
            if (path.size() > 0 && path.get(path.size() - 1) > nums[i]) {
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            dfs(i + 1, nums);
            path.remove(path.size() - 1);
        }
    }
}

全排列

  • 法1 dfs 回溯

回溯 - 图5 :::warning 注：不能用 选或不选 ，只能 for 循环回溯
用 used 数组记录重复元素 :::

class Solution {
    List<List<Integer>> res = new ArrayList();

    List<Integer> path = new ArrayList();

    public List<List<Integer>> permute(int[] nums) {
        dfs(0, nums, new boolean[nums.length]);
        return res;
    }

    void dfs(int index, int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(i + 1, nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

全排列 II

  • 法1 dfs 回溯 :::warning 注：不能用 选或不选 ，只能 for 循环回溯
    排序是前提，用 used 数组记录重复元素， 见解析。 :::

    class Solution {
   List<List<Integer>> res = new ArrayList();

  List<Integer> path = new ArrayList();
  public List<List<Integer>> permuteUnique(int[] nums) {
      Arrays.sort(nums);
      dfs(0, nums, new boolean[nums.length]);
      return res;
  }

  void dfs(int index, int[] nums, boolean[] used) {
      if (path.size() == nums.length) {
          res.add(new ArrayList(path));
          return;
      }
      for (int i = 0; i < nums.length; i++) {
          if (used[i]) {
              continue;
          }
          if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
              continue;
          }
          used[i] = true;
          path.add(nums[i]);
          dfs(i + 1, nums, used);
          path.remove(path.size() - 1);
          used[i] = false;
      }
  }
}

    分割等和子集

  • 法1 选或不选 :::warning 对每个元素选或不选分支，枚举所有可能，遇到满足条件的 return true :::

    class Solution {

  boolean flag = false;

  public boolean canPartition(int[] nums) {
      int target = 0;
      for (int i = 0; i < nums.length; i++) {
          target += nums[i];
      }
      if ((target & 1) == 1) {
          return false;
      }
      dfs(nums, 0, 0, target);
      return flag;
  }

  void dfs(int[] nums, int index, int sum, int target) {
      if (sum * 2 >= target) {
          if (sum * 2 == target) {
              flag = true;
          }
          return;
      }
      if (index >= nums.length) {
          return;
      }
      dfs(nums, index + 1, sum, target);
      dfs(nums, index + 1, sum + nums[index], target);
  }
}

  • 法2 转化为 0-1 背包 :::warning 状态定义：dp[i][j] 表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
    dp[i−1][j]，即不选 nums[i] 的结果
    dp[i][j] = true，即 dp[i][nums[i]] = true
    dp[i−1][j−nums[i]]，即选 nums[i] 的结果 :::

    class Solution {

  public boolean canPartition(int[] nums) {
      int target = 0;
      for (int i = 0; i < nums.length; i++) {
          target += nums[i];
      }
      if ((target & 1) == 1) {
          return false;
      }
      //dp[i] = dp[i - nums[i]]
      boolean[][] dp = new boolean[nums.length][target / 2 + 1];
      dp[0][0] = false;
      for (int i = 1; i < nums.length; i++) {
          for (int j = 0; j <= target / 2; j++) {
              //dp[i][nums[i]] = true;
              if (nums[i] == j) {
                  dp[i][j] = true;
                  continue;
              }
              //不选 nums[i]
              dp[i][j] = dp[i - 1][j];
              //选 nums[i]
              if (j > nums[i]) {
                  dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
              }
          }
      }
      return dp[nums.length - 1][target / 2];
  }
}

    :::warning 空间优化：二维数组优化为一维数组，注意应该从后往前遍历，若从前往后会覆盖前值，导致值传递错误。 ::: 回溯 - 图6

    class Solution {

  public boolean canPartition(int[] nums) {
      int target = Arrays.stream(nums).sum();
      if ((target & 1) == 1) {
          return false;
      }
      boolean[] dp = new boolean[target / 2 + 1];
      dp[0] = true;
      for (int i = 1; i < nums.length; i++) {
          for (int j = target / 2; j >= nums[i]; j--) {
              //已满足条件
              if (dp[target / 2]) {
                  return true;
              }
              //(不选 nums[i]) || (选 nums[i])
              dp[j] = dp[j] || dp[j - nums[i]];
          }
      }
      return dp[target / 2];
  }
}

    划分为k个相等的子集

  • 法1 对 k 个桶插入数字 :::warning 剪枝 :::

    class Solution {

  public boolean canPartitionKSubsets(int[] nums, int k) {
      int sum = Arrays.stream(nums).sum();
      if (k > sum || sum % k != 0) {
          return false;
      }
      sum = sum / k;
      //桶
      int[] bucket = new int[k];
      // 降序排列
      Arrays.sort(nums);
      int left = 0, right= nums.length - 1;
      while (left < right) {
          int temp = nums[left];
          nums[left] = nums[right];
          nums[right] = temp;
          left++;
          right--;
      }
      return dfs(nums, bucket, 0, sum);
  }

  boolean dfs(int[] nums, int[] bucket, int index, int sum){
      if (index >= nums.length) {
          return true;
      }
      for (int i = 0; i < bucket.length; i++) {
          if (i > 0 && index == 0) {
              break;
          } 
          if (i > 0 && bucket[i] == bucket[i - 1]) {
              continue;
          } 
          if (nums[index] + bucket[i] > sum) {
              continue;
          }
          bucket[i] += nums[index];
          if (dfs(nums, bucket, index + 1, sum)) {
              return true;
          }
          bucket[i] -= nums[index];
      }
      return false;
  }
}

    N 皇后

    class Solution {

  List<List<String>> res = new ArrayList<>();

  /* 输入棋盘的边长n，返回所有合法的放置 */
  public List<List<String>> solveNQueens(int n) {
      // "." 表示空，"Q"表示皇后，初始化棋盘
      char[][] board = new char[n][n];
      for (char[] c : board) {
          Arrays.fill(c, '.');
      }
      backtrack(board, 0);
      return res;
  }

  public void backtrack(char[][] board, int row) {
      // 每一行都成功放置了皇后，记录结果
      if (row == board.length) {
          res.add(charToList(board));  
          return;
      }
      int n = board[row].length;
      // 在当前行的每一列都可能放置皇后
      for (int col = 0; col < n; col++) {
          // 排除可以相互攻击的格子
          if (!isValid(board, row, col)) {
              continue;
          }
          // 做选择
          board[row][col] = 'Q';
          // 进入下一行放皇后
          backtrack(board, row + 1);
          // 撤销选择
          board[row][col] = '.';
      }
  }

  /* 判断是否可以在 board[row][col] 放置皇后 */
  public boolean isValid(char[][] board, int row, int col) {
      int n = board.length;
      // 检查列是否有皇后冲突
      for (int i = 0; i < n; i++) {
          if (board[i][col] == 'Q') {
              return false;
          }
      }
      // 检查右上方是否有皇后冲突
      for (int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++) {
          if (board[i][j] == 'Q') {
              return false;
          }
      }
      // 检查左上方是否有皇后冲突
      for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
          if (board[i][j] == 'Q') {
              return false;
          }
      }
      return true;
  }

  public List charToList(char[][] board) {
      List<String> list = new ArrayList<>();

      for (char[] c : board) {
          list.add(String.copyValueOf(c));
      }
      return list;
  }
}

    解数独

    class Solution {
  public void solveSudoku(char[][] board) {
      /**
       * 记录某行，某位数字是否已经被摆放
       */
      boolean[][] row = new boolean[9][9];
      /**
       * 记录某列，某位数字是否已经被摆放
       */
      boolean[][] col = new boolean[9][9];
      /**
       * 记录某 3x3 宫格内，某位数字是否已经被摆放
       */
      boolean[][] block = new boolean[9][9];

      for (int i = 0; i < 9; i++) {
          for (int j = 0; j < 9; j++) {
              if (board[i][j] != '.') {
                  int num = board[i][j] - '1';
                  row[i][num] = true;
                  col[j][num] = true;
                  // blockIndex = i / 3 * 3 + j / 3，取整
                  block[i / 3 * 3 + j / 3][num] = true;
              }
          }
      }
      dfs(board, row, col, block, 0, 0);
  }

  private boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) {
      // 找寻空位置
      while (board[i][j] != '.') {
          if (++j >= 9) {
              i++;
              j = 0;
          }
          if (i >= 9) {
              return true;
          }
      }
      for (int num = 0; num < 9; num++) {
          int blockIndex = i / 3 * 3 + j / 3;
          if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {
              // 递归
              board[i][j] = (char) ('1' + num);
              row[i][num] = true;
              col[j][num] = true;
              block[blockIndex][num] = true;
              if (dfs(board, row, col, block, i, j)) {
                  return true;
              } else {
                  // 回溯
                  row[i][num] = false;
                  col[j][num] = false;
                  block[blockIndex][num] = false;
                  board[i][j] = '.';
              }
          }
      }
      return false;
  }
}

    新员工考试

    06f632aabba6cf394c1546a08e4ee06.png

  • dfs 回溯

    public class HJ2022042001 {

  static int[] scores = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8};

  static int res = 0;

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int score = sc.nextInt();
      dfs(0, 0, score, 0);
      System.out.println(res);
  }

  static void dfs(int index, int cur, int score, int error) {
      if (cur == score) {
          res++;
          return;
      }
      if (error == 3 || cur > score || index == scores.length) {
          return;
      }
      //做对该题
      dfs(index + 1, cur + scores[index], score, error);
      //做错该题
      dfs(index + 1, cur, score, error + 1);
  }
}

    项目规划

    e4a984bbcd9a208e9dde625b8cb651c.png

  • 选与不选，用完全背包会超时

    public class HJ2022042702 {

  static int res = 0;

  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      //项目总数
      int n = in.nextInt();
      //3个 团队人力总和
      int[] sArr = new int[3];
      for (int i = 0; i < 3; i++) {
          sArr[i] = in.nextInt();
      }
      //n个 每个项目预估价值
      int[] vArr = new int[n];
      for (int i = 0; i < n; i++) {
          vArr[i] = in.nextInt();
      }
      //n个 每个项目所需人力
      int[][] pArr = new int[n][3];
      for (int i = 0; i < n; i++) {
          pArr[i][0] = in.nextInt();
          pArr[i][1] = in.nextInt();
          pArr[i][2] = in.nextInt();
      }
      dfs(0, 0, new int[3], vArr, pArr, sArr);
      System.out.println(res);
  }

  static void dfs(int index, int curV, int[] pUsed, int[] vArr, int[][] pArr, int[] sArr) {
      int n = vArr.length;
      res = Math.max(res, curV);
      if (index == n) {
          return;
      }
      //不选项目index
      dfs(index + 1, curV, pUsed, vArr, pArr, sArr);
      //选项目index
      for (int i = 0; i < 3; i++) {
          pUsed[i] += pArr[index][i];
      }
      //前端人力总和超过限制 || 后端人力总和超过限制 || 测试人力总和超过限制
      if (pUsed[0] > sArr[0] || pUsed[1] > sArr[1] || pUsed[2] > sArr[2]) {
          return;
      }
      dfs(index + 1, curV + vArr[index], pUsed, vArr, pArr, sArr);
      for (int i = 0; i < 3; i++) {
          pUsed[i] -= pArr[index][i];
      }
  }
}

    小美做饭

    a2130a017fbebc2af562c86d1731251.png

  • 选与不选 ```java package com.algorithm.实习.美团;

import java.util.*;

/**

  • @ClassName Test3
  • @Description 小美做菜
  • @Author bill
  • @Date 2022/3/12 17:10

  • @Version 1.0 **/ public class Test3 {

    static int res = 0;

    public static void main(String[] args) {

     Scanner scanner = new Scanner(System.in);
 //n个客人
 int n = scanner.nextInt();
 //能做菜编号
 int m = scanner.nextInt();
 //订单
 int[][] menu = new int[n][2];
 for (int i = 0; i < n; i++) {
     for (int j = 0; j < 2; j++) {
         menu[i][j] = scanner.nextInt();
     }
 }
 dfs(0, m, menu, new ArrayList(), 0);
 System.out.println(res);

    }

    static void dfs(int index, int m, int[][] menu, List list, int guests) {

     if (index == menu.length) {
     res = Math.max(guests, res);
     return;
 }
 //不选择 第 index 顾客
 dfs(index + 1, m, menu, list, guests);
 //选择 第 index 顾客
 //先判断
 if (menu[index][0] == menu[index][1] || list.contains(menu[index][0]) || list.contains(menu[index][1]) || menu[index][0] > m || menu[index][1] > m) {
     return;
 }
 list.add(menu[index][0]);
 list.add(menu[index][1]);
 dfs(index + 1, m, menu, list, guests + 1);
 list.remove(list.size() - 1);
 list.remove(list.size() - 1);

    } } ```