## Approach 1: DFS

• Time:O(2^{10})
• Space:O(2^{10})

## C++

class Solution {
public:
vector<string> ans;
dfs(num, 0, 0, 0, ans);
return ans;
}

private:
const vector<int> hours{1, 2, 4, 8};
const vector<int> minutes{1, 2, 4, 8, 16, 32};

void dfs(int n, int s, int h, int m, vector<string>& ans) {
if (n == 0) {
string time = to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m);
ans.push_back(time);
return;
}

for (int i = s; i < hours.size() + minutes.size(); ++i)
if (i < 4 && h + hours[i] < 12)
dfs(n - 1, i + 1, h + hours[i], m, ans);
else if (i >= 4 && m + minutes[i - 4] < 60)
dfs(n - 1, i + 1, h, m + minutes[i - 4], ans);
}
};


## JAVA

class Solution {
List<String> ans = new ArrayList<>();
dfs(num, 0, 0, 0, ans);
return ans;
}

private int[] hours = new int[] {1, 2, 4, 8};
private int[] minutes = new int[] {1, 2, 4, 8, 16, 32};

private void dfs(int n, int s, int h, int m, List<String> ans) {
if (n == 0) {
final String time = String.valueOf(h) + ":" + (m < 10 ? "0" : "") + String.valueOf(m);
return;
}

for (int i = s; i < hours.length + minutes.length; ++i)
if (i < 4 && h + hours[i] < 12)
dfs(n - 1, i + 1, h + hours[i], m, ans);
else if (i >= 4 && m + minutes[i - 4] < 60)
dfs(n - 1, i + 1, h, m + minutes[i - 4], ans);
}
}


## Approach 2: Bit

• Time:O(12 \cdot 60)
• Space:O(12 \cdot 60)

## C++

class Solution {
public:
vector<string> ans;

for (int h = 0; h < 12; ++h)
for (int m = 0; m < 60; ++m)
if (__builtin_popcount(h << 6 | m) == num)
ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

return ans;
}
};


## JAVA

class Solution {

for (int h = 0; h < 12; ++h)
for (int m = 0; m < 60; ++m)
if (Integer.bitCount(h) + Integer.bitCount(m) == num)
ans.add(h + (m < 10 ? ":0" : ":") + m);

return ans;
}
}