Java backtracking solution


  • 0
    S
    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> ret = new ArrayList<>();
            List<List<Integer>> hourSet = new ArrayList<List<Integer>>();
            List<List<Integer>> minSet = new ArrayList<List<Integer>>();
            List<Integer> hour = new ArrayList<>(Arrays.asList(1, 2, 4, 8));
            List<Integer> min = new ArrayList<>(Arrays.asList(1, 2, 4, 8, 16, 32));
            for (int i = 0; i <= num; i++) {
                helper(hourSet, hour, 0, 0, 0, i);
                helper(minSet, min, 0, 0, 0, i);
            }
            for (int i = 0; i <= num; i++) {
                if (i < hourSet.size() && num - i < minSet.size()) {
                    for (Integer val1 : hourSet.get(i)) {
                        for (Integer val2 : minSet.get(num - i)) {
                            if (val2 / 10 == 0) {
                                ret.add(val1 + ":0" + val2);
                            } else {
                                ret.add(val1 + ":" + val2);
                            }
                        }
                    }
                }
            }
            return ret;
        }
    
        public void helper(List<List<Integer>> resSet, List<Integer> set, int sum, int index, int n, int key) {
            if (n == key) {
                if (resSet.size() == n) {
                    resSet.add(new ArrayList<>());
                }
                resSet.get(n).add(sum);
                return;
            }
            for (int i = index; i < set.size(); i++) {
                // hour set
                if (set.size() == 4 && set.get(i) + sum > 11) {
                    break;
                }
                // min set
                if (set.size() == 6 && set.get(i) + sum > 59) {
                    break;
                }
                sum = sum + set.get(i);
                helper(resSet, set, sum, i + 1, n + 1, key);
                sum = sum - set.get(i);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.