day40.[搜索].401.二进制手表

思路

使用回溯
再使用二进制压缩状态
根据题目注意小时和分钟的剪枝

代码

var readBinaryWatch = function(num) {
  const arr = [1, 2, 4, 8, 16, 32, 1, 2, 4, 8];
  const result = [];
  let hour = 0, min = 0;
  function dfs(number, state, index) {
    if (number === 0) {
      result.push(`${hour}:${min < 10 ? '0'+min : min}`)
      return
    }
    for(let i = index; i < arr.length; i++) {
      let cur = arr[i];
      if (state & (1 << i)) continue;
      // 小时
      if (i > 5) {
        if (hour + cur > 11) continue;
        hour += cur;
        dfs(number - 1, state | (1 << i), i)
        hour -= cur;
      } else { // 分钟
        if (min + cur > 59) continue;
        min += cur;
        dfs(number - 1, state | (1 << i), i)
        min -= cur;
      } 
    }
  }
  dfs(num, 0, 0)
  return result;
};

var readBinaryWatch = function(num) {
  const result = [];
  function dfs(number, start, hour, min) {
    if (hour > 11  || min > 59) return;
    if (number === 0) {
      return result.push(`${hour}:${min < 10 ? '0'+min : min}`)  
    }
    for(let i = start; i < 10; i++) {
      dfs(number - 1, i + 1, hour + (i > 5 ? 2 ** (i-6) : 0), min + (i > 5 ? 0 : 2 ** i));
    }
  }
  dfs(num, 0, 0, 0)
  return result;
};

/**
 * @param {number} num
 * @return {string[]}
 */
var readBinaryWatch = function(num) {
  const nums = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]
  const res = []
  traceBack(num, 0, 0, 0)
  return res
  function traceBack(num, index, h, m) {
    if (h > 11 || m > 59) return;
    if (!num) {
      res.push(`${h}:${m > 9 ? m : '0'+m}`)
      return;
    }
    for(let i = index; i < nums.length; i ++) {
      traceBack(num-1, i+1, h+(i>3 ?0:nums[i]), m+(i>3?nums[i]:0))
    }
  }
};

复杂度分析

时间复杂度 #card=math&code=O%282%5EN%29)
空间复杂度 #card=math&code=O%281%29)