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) —
推荐阅读:富含膳食纤维蔬菜之红薯的保健作用 红薯怎么吃润肠通便及红薯食用禁忌 吃海带的十大好处和海带的饮食禁忌 经常食用这三种饭有助于预防肠癌 保健食品需谨慎 所谓效果是心理作用 关于预防癌症的十条饮食和生活建议 春季喝蜂蜜功效胜补品抗过敏润肺止咳 这十种食用方法让蜂蜜营养又健康 婴幼儿等四类人群不宜食用蜂蜜 教你这七招快速辨别蜂蜜的真假
- 评论列表
-
- 添加评论