Using Bitmasking Algorithm to Compute the Combinations of an Arr
- 时间:2020-09-07 12:13:31
- 分类:网络文摘
- 阅读:83 次
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) —
推荐阅读:写毛笔字作文150字 聚贤亭作文 体验实践的意义 人生就是一种承受作文500字 母爱的力量——读《天真妈妈》有感 心碎的感觉 做一个有道德的人|小学作文 写人作文我们班的xx作文 描写校园春景的作文 后勤的一天
- 评论列表
-
- 添加评论