Using Bitmasking Algorithm to Compute the Combinations of an Arr
- Time:2020-09-07 12:13:31
- Class:Weblog
- Read:28
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
Combination Algorithm using Bitmasking
The combination can also be done in Recursive backtracking. However, it can also be implemented using the Bitmasking algorithm.
The idea is to bruteforce all possible configurations (of bitmasks) in O(2^N) where N is the length of the given input set. Then once the configuration has k bit sets, we output the corresponding configuration.
The following is the Python combination implementation using bitmasking.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in (range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << i)) > 0: cur.append(i + 1) ans.append(cur) return ans |
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in (range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << i)) > 0: cur.append(i + 1) ans.append(cur) return ans
and with slight changes – reversing the bit searching – still works
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in reversed(range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << (n - i - 1))) > 0: cur.append(i + 1) ans.append(cur) return ans |
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: ans = [] for b in reversed(range(1 << n)): if bin(b).count('1') == k: cur = [] for i in range(n): if (b & (1 << (n - i - 1))) > 0: cur.append(i + 1) ans.append(cur) return ans
The recursive algorithm in C++: Recursive Combination Algorithm Implementation in C++.
Also, another interesting read: combination
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:Summits set epoch-making milestone in history of China-Arab ties
In the face of COVID-19 pandemic, China and Arab countries have
15 Macao residents qualify as candidates for deputies to nationa
Study finds genetic solution to pre-harvest sprouting in rice, w
Bodybuilders dying as coaches, judges encourage extreme measures
Malta's Marsaskala, China's Dujiangyan sign sister city agreemen
U.S. mortgage applications continue slide amid surging interest
Russian, UAE presidents discuss bilateral cooperation over phone
Hate crimes in U.S. Los Angeles County rise to highest level sin
Chinese mainland reports 4,031 new local confirmed COVID-19 case
- Comment list
-
- Comment add