DFS Java


  • 0
    M
    public class Solution {
        static final int[] h = {8, 4, 2, 1}, m = {32, 16, 8, 4, 2, 1};
        public List<String> readBinaryWatch(int num) {
            List<String> list = new ArrayList<>();
            if (num < 0 || num > 12) return list;
            for (int i = 0; i <= num; ++i) {
                List<Integer> hours = new ArrayList<>();
                dfs(i, 11, h, 0, 0, hours);
                List<Integer> mins = new ArrayList<>();
                dfs(num - i, 59, m, 0, 0, mins);
                for (int hour : hours) {
                    for (int min : mins) {
                        String minStr = String.valueOf(min);
                        if (minStr.length() < 2) minStr = "0" + minStr;
                        list.add(hour + ":" + minStr);
                    }
                }
            }
            return list;
        }
        private void dfs(int n, int max, int[] v, int start, int sum, List<Integer> list) {
            if (start == v.length) {
                if (n == 0 && sum <= max) {
                    list.add(sum);
                }
                return;
            }
            dfs(n, max, v, start + 1, sum, list);
            if (n > 0) dfs(n - 1, max, v, start + 1, sum + v[start], list);
        }
    }
    

Log in to reply
 

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