401. Binary Watch

https://leetcode.com/problems/binary-watch/

Python

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        options = [
            ("h", 8), ("h", 4), ("h", 2), ("h", 1),
            ("m", 32), ("m", 16), ("m", 8), ("m", 4), ("m", 2), ("m", 1)
        ]

        used = set()
        result = set()

        def backtrack(track, hour, minute):
            if len(track) == turnedOn:
                result.add('{h:d}:{m:02d}'.format(h=hour, m=minute))
                return

            for option in options:
                if option in used:
                    continue

                track.append(option)
                used.add(option)

                if option[0] == 'h':
                    if hour + option[1] < 12:
                        backtrack(track, hour+option[1], minute)
                else:
                    if minute + option[1] < 60:
                        backtrack(track, hour, minute+option[1])

                track.pop()
                used.remove(option)

        backtrack([], 0, 0)

        return [string for string in result]

Javascript

/**
 * H [1,2,4,8]
 * M [1,2,4,8,16,32]
 *
 * Example 1:
 * turnedOn = 1 => [0,1], [1,0]
 * turnedOn = 2 => [0,2], [2,0], [1, 1]
 */

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function (turnedOn) {
  if (turnedOn >= 9) return [];
	const hourDigits = [1, 2, 4, 8];
	const minDigits = [1, 2, 4, 8, 16, 32];
	const n = turnedOn;
	const result = [];

	for (let i = 0; i <= n; i++) {
		const hours = createDigit(hourDigits, i);
		const mins = createDigit(minDigits, n - i);
		 // console.log(hours, i)
		 // console.log(mins, n - i)

     for (hour of hours) {
      for (min of mins) {
        if (hour >= 12 || min >= 60) break;
        result.push(`${hour}:${padZero(min)}`);
      }
     }
	}
	return result;
};

function createDigit(list, max) {
	const result = [];
	pickByMax(list, max, 0, [], result);
	return result;
}

function pickByMax(ary, max, start, record = [], result) {
	if (record.length === max) {
		const sum = record.reduce((acc, num) => acc + num, 0);
		result.push(sum);
		return;
	}

	for (let i = start; i < ary.length; i++) {
		record.push(ary[i]);
		pickByMax(ary, max, i + 1, record, result);
		record.pop();
	}
}

function padZero(num) {
	if (!num) return "00";

	const target = 2;
	const max = Math.max(target - num.toString().length, 0);
	const pad = "0".repeat(max);
	return `${pad}${num}`;
}