LeetCode Binary Watch问题回溯法求解求助（代码异常）

嘿，我看你在用回溯法解LeetCode的Binary Watch问题时卡壳了，代码还没写完就走不通了对吧？先帮你理清楚这个问题的核心规则，再把你的代码逻辑补全修复：

• 手表有4个小时灯，对应数值[1,2,4,8]，亮灯总和得在0-11之间
• 6个分钟灯，对应数值[1,2,4,8,16,32]，亮灯总和得在0-59之间
• 给定num个亮灯，要输出所有合法的小时:分钟格式（分钟不足两位补0）

你当前代码的核心问题 #

从你给出的截断代码来看，主要有这几个漏洞：

• 循环里没区分小时灯和分钟灯的边界，也没处理回溯最关键的选择-递归-撤销选择流程
• 没对小时和分钟的合法范围做校验，容易生成像12:00这种无效时间
• 代码逻辑不完整，循环内的处理被截断，没法正常执行

修正后的完整回溯代码 #

import java.util.ArrayList;
import java.util.List;

public class BinaryWatch {
    // 提前定义小时和分钟灯对应的数值，不用每次创建列表
    private static final int[] HOUR_OPTIONS = {1, 2, 4, 8};
    private static final int[] MIN_OPTIONS = {1, 2, 4, 8, 16, 32};

    public static List<String> readBinaryWatch(int num) {
        List<String> possibleTimes = new ArrayList<>();
        // 启动回溯：参数分别是当前小时总和、分钟总和、剩余要选的灯数、小时灯的起始索引、分钟灯的起始索引
        backtrack(possibleTimes, 0, 0, num, 0, 0);
        return possibleTimes;
    }

    private static void backtrack(List<String> result, int hourSum, int minSum, int remainLights, int hourStart, int minStart) {
        // 终止条件：没有剩余灯要选，且时间合法
        if (remainLights == 0) {
            if (hourSum <= 11 && minSum <= 59) {
                // 格式化分钟，不足两位补0
                String minStr = minSum < 10 ? "0" + minSum : String.valueOf(minSum);
                result.add(hourSum + ":" + minStr);
            }
            return;
        }

        // 先选小时灯：从hourStart开始选，避免重复组合（比如先选1再选2和先选2再选1是同一个时间）
        for (int i = hourStart; i < HOUR_OPTIONS.length; i++) {
            // 做选择：加上当前小时灯的数值，剩余灯数减1，下一次从i+1开始选（避免重复）
            backtrack(result, hourSum + HOUR_OPTIONS[i], minSum, remainLights - 1, i + 1, minStart);
            // 这里不用手动撤销，因为递归传递的是新的数值，栈帧返回后原hourSum自动恢复
        }

        // 再选分钟灯：同理，从minStart开始选，避免重复
        for (int i = minStart; i < MIN_OPTIONS.length; i++) {
            backtrack(result, hourSum, minSum + MIN_OPTIONS[i], remainLights - 1, hourStart, i + 1);
        }
    }

    public static void main(String[] args) {
        // 测试用例：输入1，输出所有亮1个灯的合法时间
        System.out.println(readBinaryWatch(1));
    }
}

关键逻辑说明 #

• 避免重复组合：通过hourStart和minStart参数，确保每次选灯只从当前索引往后挑，不会生成重复的时间组合
• 合法性校验：在终止条件里检查小时≤11、分钟≤59，直接过滤掉无效时间
• 回溯的简洁实现：这里没有用列表记录选中的灯，而是直接传递更新后的总和，递归返回时原数值自动恢复，省去了手动增删元素的麻烦
• 格式规范：严格按照题目要求格式化分钟，保证输出的时间格式正确

可选的另一种写法（显式处理选择与撤销） #

如果你想更直观地看到回溯的选择和撤销过程，也可以用列表记录选中的灯，代码如下：

private static void backtrack(List<String> result, List<Integer> selected, int remainLights) {
    if (remainLights == 0) {
        int hourSum = 0, minSum = 0;
        for (int num : selected) {
            if (num <= 8) hourSum += num;
            else minSum += num;
        }
        if (hourSum <=11 && minSum <=59) {
            String minStr = minSum <10 ? "0"+minSum : String.valueOf(minSum);
            result.add(hourSum + ":" + minStr);
        }
        return;
    }
    // 所有可选灯的合并数组
    int[] allLights = {1,2,4,8,1,2,4,8,16,32};
    // 从最后一个选中的灯的下一个索引开始选，避免重复
    int start = selected.isEmpty() ? 0 : selected.size();
    for (int i=start; i<allLights.length; i++) {
        selected.add(allLights[i]);
        backtrack(result, selected, remainLights-1);
        selected.remove(selected.size()-1); // 撤销选择
    }
}

不过这种写法效率稍低，因为需要频繁操作列表，还是第一种写法更高效。

内容的提问来源于stack exchange，提问作者Jeevi