2025-07-27 11:39

刷题刷的觉得自己是个傻子

LC 91 解码方法

动态规划

这道题我一开始一直没能理解这两行代码

1 2	`if (one >= 1 && one <= 9) dp[i] += dp[i-1]; if (two >= 10 && two <= 26) dp[i] += dp[i-2];`

我一直在思考为什么 dp[i] += dp[i-1]，dp[i] += dp[i-2]。想了一个半小时后我终于茅塞顿开！

分析第 i 个字符可能的解码方式

第 i 个字符 s[i-1] 可以单独解码吗？
- 如果 s[i-1] 是 ‘1’~’9’，那么它可以单独解码为一个字母；
- 这种情况下，所有前 i-1 个字符的解码方式（dp[i-1]）都可以延续下来，接上这个单独的字符。
  所以 dp[i] += dp[i-1]，因为dp[i-1]的解码方法都被延续下来了

第 i 个字符与第 i-1 个字符合起来是否能解码？

第 i-1 和 i 两个字符组成的字符串 s[i-2..i-1] 是不是合法的两位数？合法区间是 10~26。
如果是，那么这两个字符可以合起来表示一个字母；

此时，所有前 i-2 个字符的解码方式（dp[i-2]）都可以延续下来，接上这两个字符合起来的字母。

public class DecodeWays {
    public static int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;
        int[] dp = new int[n+1];
        dp[0] = 1; dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            int one = s.charAt(i-1) - '0';
            int two = Integer.parseInt(s.substring(i-2, i));

            if (one >= 1 && one <= 9) dp[i] += dp[i-1];
            if (two >= 10 && two <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("123")); // 输出 3
    }
}

总结：动态规划的核心是明确dp[i]状态是什么，找到状态转化方程，常用于以下类型:

求最值（最大、最小、最多、最少）
求方案数（有多少种方法、路径、可能）
子结构可重复利用
状态由一个或多个维度组成（位置、容量、次数等）

LC 2560 打家劫舍

打家劫舍
看到这题我的思路是这样的:

把原数组复制并排序；
从第 k 小的值开始尝试，试一试能不能选出 k 个不相邻的数字，最大值不超过它；
如果不行，就继续试下一个更大的数（k+1 小、k+2 小…）；

每次都从头找一遍，排除相邻的数字。
以下是我写的代码,不出意外的没有完全通过，A了0.66

class Solution {
    public int minCapability(int[] nums, int k) {
    //        int left = Arrays.stream(nums).min().getAsInt();
        int[] nums1 = new int[nums.length];
        ArrayList list = new ArrayList<>();
        ArrayList<Integer> index = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        System.arraycopy(nums, 0, nums1, 0, nums.length);
        Arrays.sort(nums1);
        //设置最优解
        int money1 = nums1[k - 1];
        int x = k-1;
        list.add(money1);

        for (int i = 0; i < nums1.length; i++) {
            map.put(nums[i], i);
        }
        index.add(map.get(money1));


        //最优解第K小的值正好，寻找K-1个比第K小值小的数，如果找不到则退而求起次值
        // 且找到数的小标不能连续，需要用递归
        while (list.size() < k) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < money1 && add(index,i)) {
                    list.add(nums[i]);
                    index.add(map.get(nums[i]));
                }
//                if (nums[i]==money1){
//                    continue;
//                }
//                if (list.size() < k && nums[i] > money1) {
//
//                    money1 = nums1[x+1];
//                    x++;
//                    list.clear();
//                    index.clear();
//                    list.add(money1);
//                    index.add(map.get(money1));
//                    break;
//
//                }
            }
            if (list.size() < k) {
                money1 = nums1[x+1];
                x++;
                list.clear();
                index.clear();
                list.add(money1);
                index.add(map.get(money1));
            }
        }
        return money1;
    }
     public boolean add(ArrayList index, int x){

        for (int i = 0; i <index.size(); i++){
            if (Math.abs((Integer) index.get(i) -x)==1){
                return false;
            }
        }
       return true;
    }
}

官方的答案是用二分+贪心,看到代码的时候我很疑惑，为什么直接使用i+=2，我在想不会出现一种不规则的选取（如i=1,4,7,9,13等）导致贪心函数没找出来，然后进而影响二分算法，实则不然，经过我仔细研究代码后发现，这段代码很巧妙，只要找出了K个最小值即可，就说明maxVal的范围偏大，而不是枚举出所有的组合方式。为什么我想不出来这样的解法呢！

class Solution {
    public int minCapability(int[] nums, int k) {
        int left = Arrays.stream(nums).min().getAsInt();
        int right = Arrays.stream(nums).max().getAsInt();

        while (left < right) {
            int mid = (left + right) / 2;
            if (canPick(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    // 判断是否能选出 k 个不相邻的元素，且每个 ≤ maxVal
    private boolean canPick(int[] nums, int k, int maxVal) {
        int count = 0;
        int i = 0;
        while (i < nums.length) {
            if (nums[i] <= maxVal) {
                count++;
                i += 2; // 跳过一个，保证不相邻
            } else {
                i++;
            }
        }
        return count >= k;
    }
}

LC 最热 42

接雨水

分析题目花了十分钟，本想着用几何法:

1 2	`ans += 容器总高度 * 宽度 - 中间所有柱子的高度`

所以我的思路是双指针，一个left和right,固定一个位置 i，获取到i左边的最大值和i右边的最大值，这样就可以获取到right-left区间的雨水了
但是这个边界问题很容易出错，所以果不其然没有通过。
而正确的思路应该是:
water[i] = min(leftMax[i], rightMax[i]) - height[i]
同样使用双指针,记录左右两边最大值，这样就很简单了

public static int trap(int[] height) {
    int n = height.length;
    if (n < 3) return 0; // 少于三个柱子肯定不能接水

    int ans = 0;

    for (int i = 1; i < n - 1; i++) {
        // 找左边最高
        int leftMax = height[i];
        for (int l = i - 1; l >= 0; l--) {
            leftMax = Math.max(leftMax, height[l]);
        }

        // 找右边最高
        int rightMax = height[i];
        for (int r = i + 1; r < n; r++) {
            rightMax = Math.max(rightMax, height[r]);
        }

        // 当前位置可接水量
        int water = Math.min(leftMax, rightMax) - height[i];
        if (water > 0) {
            ans += water;
        }
    }

    return ans;
}

LC 438

找到字符串中所有字母异位词

看到这题，我刚心里暗喜，这么简单，这不直接秒了吗？我直接就是将P转化成ASCII值，然后循环S，每次取3个字符，比对一下就好了

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length()-p.length()+1; i++){
            String substring = s.substring(i, i + p.length());
            if (isAnagram(substring,p)){
                list.add(i);
            }
        }
        return list;
    }

    private static boolean isAnagram(String substring, String p) {
        char[] chars = substring.toCharArray();
        char[] chars1 = p.toCharArray();
        Arrays.sort(chars);
        Arrays.sort(chars1);
        return Arrays.equals(chars, chars1);
    }
}

然后当我看到结果，不是你这案例找茬是吧

然后我就去看答案，发明答案的人真是个天才，使用的方法依然是滑动窗口，不过他用两个数组记录了p和s的字符数，每次只需要替换一个字符，确实比我自己写的高效

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s.length() < p.length()) return list;

        int[] pCount = new int[26]; // 记录 p 中每个字符出现的次数
        int[] sCount = new int[26]; // 当前窗口中字符的统计

        // 初始化 pCount 和第一个窗口的 sCount
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(pCount, sCount)) list.add(0);

        // 开始滑动窗口
        for (int i = p.length(); i < s.length(); i++) {
            // 右移窗口：添加新字符
            sCount[s.charAt(i) - 'a']++;
            // 移除最左侧的字符
            sCount[s.charAt(i - p.length()) - 'a']--;

            if (Arrays.equals(pCount, sCount)) list.add(i - p.length() + 1);
        }

        return list;
    }
}

LC 560

和为 K 的子数组

那这题第一眼先来暴力循环试试,最后也是循环出来了

class Solution {
    public int subarraySum(int[] nums, int k) {
          int count = 0;
        int left = 0;
        int right ;
        int sun = 0;
        for (left=0; left < nums.length; left++){
             sun = 0;
            for (right=left; right < nums.length; right++){
                sun += nums[right];
                if (sun == k){
                    count++;
                }
            }
        }
        return count;
    }
}

不过还有时间复杂度更小的方法：前缀和+哈希
- 优化思路的核心：前缀和
  ✅ 定义「前缀和」：
- 设 prefixSum[i] 表示数组前 i 个元素的和（不含第 i 个）：
  1
  prefixSum[i] = nums[0] + nums[1] + ... + nums[i - 1]
- 那么：从 i 到 j 的子数组之和 sum(i~j) 为：
  1
  sum(i~j) = prefixSum[j + 1] - prefixSum[i]
  也就是说：两个前缀和的差值，就是一个子数组的和。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1); // 前缀和为0的次数为1

        for (int num : nums) {
            sum += num;
            if (preSum.containsKey(sum - k)) {
                count += preSum.get(sum - k);
            }
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

LC 239

滑动窗口最大值
这题不是很简单吗，怎么会是困难题，直接两个指针滑动，找最大值

public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length-k+1; i++) {
      int  x= findMax(nums, i, i+k-1);
      res[i] = x;
    }
    return res;
}
public int findMax(int[] nums,int left,int right) {
    int max = nums[left];
    for (int i = left; i <= right; i++) {
        max = Math.max(max, nums[i]);
    }
    return max;
}

好好好是我大意了

正确解法是双端队列

维护双端队列：

用Deque存放元素的索引。在任何时刻，Deque的头部总是滑动窗口中的最大值的索引。那么当窗口滑动时，我们只取Deque的头部即可获取最大值。

滑动窗口滑动：

移除窗口最左侧的元素：如果Deque头部元素的索引已经超出当前窗口的范围（即j - k + 1之前的元素），那么从头部移除该元素。
维护单调递减性：将当前元素和Deque尾部元素比较，如果当前元素比尾部元素大，那么尾部元素不可能是当前滑动窗口的最大值，那我们移除尾部元素。重复此操作，直至Deque中的所有元素都大于当前元素，即可保持单调递减。

添加当前元素：将当前元素的索引加入Deque。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k == 0) return new int[0];

        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // 存储下标

        for (int i = 0; i < n; i++) {
            // 1. 移除不在窗口内的下标
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 2. 保持队列递减（从队尾移除比当前值小的）
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 3. 加入当前元素索引
            deque.offerLast(i);

            // 4. 形成窗口后写入结果
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return res;
    }
}

总结

🔍 举个例子来对比
假设：nums = [1, 3, 2, 5, 4], k = 3
🚫 暴力法：

窗口 [1, 3, 2] → max = 3
窗口 [3, 2, 5] → max = 5
窗口 [2, 5, 4] → max = 5
→ 每次都重新扫描窗口中的 3 个元素，重复判断

✅ Deque 单调队列法：
我们维护一个队列，始终让队列的头是当前窗口的最大值。

插入 1 → [0]
插入 3 → 弹出 1 → [1]
插入 2 → 保留 → [1,2] → 当前窗口最大值：nums[1]=3
插入 5 → 弹出 2，弹出 3 → [3]
插入 4 → 保留 → [3,4] → 当前窗口最大值：nums[3]=5
你会发现：我们没有“重复”找最大值，而是动态维护了它！

LC 76

最小覆盖子串
刚看上去，这题我的思路是只要是覆盖字串，开头第一个字符必然在字符传t中，所以我先用Set将字串t存起来，然后而且只要找到一个覆盖字串的话，就直接跳到下一个是字符t中的任意一个字符开始循环找下一个覆盖字串

class Solution {
    public String minWindow(String s, String t) {
             if (s.length() < t.length()) {
            return "";
        }
     int[] tCount = new int[256];
     for (char c : t.toCharArray()) {
         tCount[c - 'A']++;
     }
     int[] sCount = new int[256];
     Set<Character> missing = new HashSet<>();
     for (char c : t.toCharArray()) {
         missing.add(c);
     }
     int left = 0, right = 0;
     int next = 0;
     int minLen = Integer.MAX_VALUE;
     String res = "";
     for (int i = 0; i < s.length(); i++){
         char c = s.charAt(i);
         if (missing.contains(c)){
             sCount[c - 'A']++;
             if(Arrays.equals(tCount, sCount)){
                 return t;
             }
             left = i;
             break;
         }
     }
     for (int i =left+1; i < s.length(); i++){
         char c = s.charAt(i);
         if (missing.contains(c)){
             if (sCount[c-'A']<tCount[c-'A']){
                 sCount[c - 'A']++;
             }
             if (next==0){
                 next = i;
             }
         }
         if(Arrays.equals(tCount, sCount)){
             if (minLen > i - left+ 1){
                 res = s.substring(left, i + 1);
             }
             minLen = Math.min(minLen, i - left + 1);
             i=next;
             left = next;
             sCount = new int[256];
             sCount[s.charAt(next) - 'A']++;
             next=0;
         }
     }
     return res;
    }
}

很遗憾，269个案例通过了265个，遇见超时了，气死我了！

LC 54

螺旋矩阵

这题第一眼看上去很懵，自然观察思考后，可以设置四个变量，分别表示最上面的行，最下面的行，最右边的列，最左边的列，有这四个边界去循环就可以了

public List<Integer> spiralOrder(int[][] matrix) {
   int m = matrix.length;
   int n = matrix[0].length;
   List<Integer> list = new ArrayList<>();
   int top = 0;
   int left = 0;
   int right = n-1;
   int bottom = m-1;
  while (top <= bottom && left <= right){
      //最上面行
      for (int i = left; i <= right; i++) {
          list.add(matrix[top][i]);
      }
      top++;
      //最右边列
      for (int i = top; i <= bottom; i++) {
          list.add(matrix[i][right]);
      }
      right--;
      //最下面行
      if (top <= bottom){
          for (int i = right; i >= left; i--) {
              list.add(matrix[bottom][i]);
          }
          bottom--;
      }
      //最左边列
      if (left <= right){
          for (int i = bottom; i >= top; i--) {
              list.add(matrix[i][left]);
          }
          left++;
      }
  }
   return  list;
   }

LC 160 相交链表

相交链表

双指针
两个指针分别走完 A + B 和 B + A，它们要么在交点相遇，要么都走到 null。
1
2
A: a1 → a2 → c1 → c2 → c3 B: b1 → b2 → b3 → c1 → c2 → c3

相交节点是 c1

p1 走的是路径：a1→a2→c1→c2→c3→null→b1→b2→b3→c1

p2 走的是路径：b1→b2→b3→c1→c2→c3→null→a1→a2→c1
所以最终两个指针都会在 c1 相遇。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode p1 = headA;
        ListNode p2 = headB;

        // 两个指针交替走完对方的链表，最终在交点相遇或都为 null
        while (p1 != p2) {
            p1 = (p1 == null) ? headB : p1.next;
            p2 = (p2 == null) ? headA : p2.next;
        }

        return p1; // 如果有交点，就是交点；否则为 null
    }
}

LC 206 反转链表

反转链表

可以用三个指针实现反转链表

prev：上一个节点（初始化为 null）
curr：当前节点（从 head 开始）

next：暂存 curr 的下一个节点（防止断链）
例如初始链表:

1	`head -> 1 -> 2 -> 3 -> null`

第一次交换后

1 2	`prev: 1 -> null curr: 2 -> 3 -> null`

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;     // 上一个节点
        ListNode curr = head;     // 当前节点

        while (curr != null) {
            ListNode next = curr.next; // 暂存下一个节点
            curr.next = prev;          // 反转指针
            prev = curr;               // prev 前进一步
            curr = next;               // curr 前进一步
        }

        return prev; // prev 最终指向新的头结点
    }
}

LC 25. K 个一组翻转链表

K 个一组翻转链表

递归+反转链表
刚看这个题的时候我想，我会反转链表，怎么给他转换一下，但是我没想到用递归，这个递归就完美解决了问题
每次都只反转K个，将剩下的交给下一次递归！

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 检查当前是否有 k 个节点
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            if (cur == null) return head; // 不足 k 个，不反转
            cur = cur.next;
        }

        // 2. 翻转前 k 个节点
        ListNode newHead = reverse(head, cur); // 左闭右开 [head, cur)

        // 3. 递归处理后续节点，并接上
        head.next = reverseKGroup(cur, k);

        return newHead;
    }

    // 反转区间 [start, end) 的节点，end 不翻转（右开）
    private ListNode reverse(ListNode start, ListNode end) {
        ListNode prev = null;
        ListNode curr = start;

        while (curr != end) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev; // 反转后的头结点
    }
}

LC 148. 排序链表

排序链表

我第一思路是直接遍历一遍链表，用数组存起来，数组排序。然后替换值。这属于是投机取巧了。再来看看正确的解法吧

递归代码逐步解析

找到中位数，一个快指针走两步，一个慢指针走一步，当快指针走到头时，慢指针肯定走到中间了
- 为什么要找中位数？目的是找到中位数，可以分割成左右两个链表，分别排序，然后合并一下
  1
  2
  3
  4
  5
  6
  ListNode slow=head;ListNode fast=head.next; //找到中位数 while (fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; }

递归调用，将第一次分割的两个左右链表，都当作一个链表继续去分割成小的左右链表，知道不能分割为止

ListNode mid = slow.next;
 slow.next = null;             // 必须先断链！
 ListNode left = sortList(head);
 ListNode right = sortList(mid); // 再递归右半部分

此时整体上是已经递归到最底层了也就是被分割成了很多小链表了，合并两两小链表，返回合并后的大链表，知道递归到最上层
1
ListNode res= merge(left,right);

示例流程

sortList([-1,5,3,4,0])
├─ left: [-1,5,3]
│   ├─ left: [-1]
│   └─ right: [5,3]
│        ├─ left: [5]
│        └─ right: [3]
│        └─ merge → [3,5]
│   └─ merge([-1], [3,5]) → [-1,3,5]
└─ right: [4,0]
 ├─ left: [4]
 └─ right: [0]
 └─ merge → [0,4]
└─ merge([-1,3,5], [0,4]) → [-1,0,3,4,5]

public ListNode sortList(ListNode head) {
    if (head==null||head.next==null) return head;
    ListNode slow=head;ListNode fast=head.next;
    //找到中位数
    while (fast!=null&&fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;             // 必须先断链！
    ListNode left = sortList(head);
    ListNode right = sortList(mid); // 再递归右半部分
    ListNode res= merge(left,right);
    return res;
}
public ListNode merge(ListNode left,ListNode right){
    ListNode dummy=new ListNode(0);
    ListNode temp = dummy;
    while(left != null && right != null){
        if (left.val < right.val){
            temp.next = left;
            left = left.next;
            temp=temp.next;
        }else {
            temp.next = right;
            right = right.next;
            temp=temp.next;
        }
    }
    while (left !=null){
        temp.next = left;
        left = left.next;
        temp=temp.next;
    }
    while (right !=null){
        temp.next = right;
        right = right.next;
        temp=temp.next;
    }
    return dummy.next;
}

LC 46. 全排列

全排列

递归＋回溯

nums = [1, 2, 3] 的回溯全排列展开过程

第一层：
i = 0 → 选择 1 → path = [1]
    第二层：
    i = 0 → 已在 path 中，跳过
    i = 1 → 选择 2 → path = [1, 2]
        第三层：
        i = 0 → 已在 path 中，跳过
        i = 1 → 已在 path 中，跳过
        i = 2 → 选择 3 → path = [1, 2, 3]
            ✅ 满足条件，加入结果：result.add([1, 2, 3])
        🔙 回溯：移除 3 → path = [1, 2]
    🔙 回溯：移除 2 → path = [1]

    i = 2 → 选择 3 → path = [1, 3]
        第三层：
        i = 0 → 已在 path 中，跳过
        i = 1 → 选择 2 → path = [1, 3, 2]
            ✅ 满足条件，加入结果：result.add([1, 3, 2])
        🔙 回溯：移除 2 → path = [1, 3]
    🔙 回溯：移除 3 → path = [1]
🔙 回溯：移除 1 → path = []

public static List<List<Integer>> permute(int[] nums) {
 ArrayList path = new ArrayList();
 List<List<Integer>> result =new ArrayList();
 balance(path, result,nums);
 return result;
 }
 public static void balance(ArrayList<Integer> path, List<List<Integer>> list, int[] nums) {
     if (path.size() == nums.length){
         ArrayList arrayList = new ArrayList();
         for (int i = 0; i < path.size(); i++) {
             arrayList.add(path.get(i));
         }
         list.add(arrayList);
         return;
     }
     for (int i = 0; i <nums.length;i++){
         if(!path.contains(nums[i])) {
             path.add(nums[i]);
             balance(path, list, nums);
             path.remove(path.size() - 1);
         }
     }
 }

LC 39. 组合总和

组合总和

回溯

/**
    * 主函数：寻找所有可以组成 target 的组合
    * @param candidates 可选的数字数组（正整数）
    * @param target     目标和
    * @return 所有组合的列表，每个组合是一个整数列表
    */
   public static List<List<Integer>> combinationSum(int[] candidates, int target) {
       List<List<Integer>> res = new ArrayList<>(); // 存放所有合法组合结果
       backtrack(res, candidates, 0, target, new ArrayList<>()); // 开始回溯搜索
       return res;
   }

   /**
    * 回溯函数：在 candidates 中从 index 开始选择数字，寻找所有和为 target 的组合
    * @param res        结果集，收集所有满足条件的组合
    * @param candidates 候选数字数组
    * @param index      当前搜索的起始位置（为了避免重复组合，始终从当前及后面开始）
    * @param target     当前剩余的目标和
    * @param path       当前路径（正在构建的组合）
    */
   public static void backtrack(List<List<Integer>> res, int[] candidates, int index, int target, List<Integer> path) {
       // ✅ 剪枝条件：剩余值 < 0，说明当前组合超了，直接返回
       if (target < 0) return;

       // 🎯 找到一个合法组合（路径之和刚好等于 target）
       if (target == 0) {
           res.add(new ArrayList<>(path)); // 注意要复制 path，否则后续回溯会修改
           return;
       }

       // 从当前 index 开始尝试加入 candidates[i] 到组合中
       for (int i = index; i < candidates.length; i++) {
           // 选择 candidates[i]
           path.add(candidates[i]);

           // 递归调用：因为一个数字可以无限使用，所以递归时传 i 而不是 i + 1
           backtrack(res, candidates, i, target - candidates[i], path);

           // 回溯：撤销选择，尝试下一个数字
           path.remove(path.size() - 1);
       }
   }

LC 22. 括号生成

括号生成

✅ 思路讲解
合法括号组合满足：

任意前缀中左括号 ( 数量 ≥ 右括号 ) 数量。
最终左右括号数量必须相等，且都为 n。
用回溯法，每次选择添加 ( 或 )：
只有当左括号 < n 时，才能添加 (；
只有当右括号 < 左括号数量时，才能添加 )。

以 n = 2 为例，整个过程会尝试这些步骤（大致流程）：

start: ""
加左括号 -> "("
再加左括号 -> "(("
不能再加左了，加右 -> "(()"
再加右 -> "(())" ✅

回溯一次，变成 "(()"，尝试别的路径
再回溯，变成 "(", 尝试加右 -> "()"
再加左 -> "()("，再加右 -> "()()" ✅

import java.util.*;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    // 回溯函数
    private void backtrack(List<String> res, StringBuilder current, int open, int close, int max) {
        // 终止条件：左右括号都用完
        if (current.length() == max * 2) {
            res.add(current.toString());
            return;
        }

        // 可以添加左括号
        if (open < max) {
            current.append('(');
            backtrack(res, current, open + 1, close, max);
            current.deleteCharAt(current.length() - 1); // 回溯
        }

        // 可以添加右括号（必须保证右括号 < 左括号）
        if (close < open) {
            current.append(')');
            backtrack(res, current, open, close + 1, max);
            current.deleteCharAt(current.length() - 1); // 回溯
        }
    }

    // 示例测试
    public static void main(String[] args) {
        GenerateParentheses gp = new GenerateParentheses();
        List<String> result = gp.generateParenthesis(3);
        System.out.println(result);
    }
}