大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“找出所欲偶相加之和为n的k个数的组合。”
2、题目描述
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1： 输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2： 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
二、解题
1、思路分析
题意要我们找出所有相加之和为 n 的 k 个数的组合，组合中只有1-9的数字，并且每组组合不能重复。
这意味着这个组合中包含9个数字，可以将原问题转化为找出1-9中满足以下条件的集合：
- 大小为k
- 集合中元素的和为n
这道题可以使用枚举的方式来解题，序列中有9个数，每个数有被选中和不被选中两种状态，状态的总数是29，所以可以用一个9位二进制数来记录当前所有位置的状态。
按顺序枚举[0,2p-1]中的所有整数的时候，通过位运算的方法得到对应的自己序列，然后再判断大小是否为k，以及集合中元素的和是否为n，如果满足，就返回答案。
2、代码实现
代码参考：
class Solution { List<Integer> temp = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); public List<List<Integer>> combinationSum3(int k, int n) { for (int mask = 0; mask < (1 << 9); ++mask) { if (check(mask, k, n)) { ans.add(new ArrayList<Integer>(temp)); } } return ans; } public boolean check(int mask, int k, int n) { temp.clear(); for (int i = 0; i < 9; ++i) { if (((1 << i) & mask) != 0) { temp.add(i + 1); } } if (temp.size() != k) { return false; } int sum = 0; for (int num : temp) { sum += num; } return sum == n; } }
3、时间复杂度
时间复杂度：O(M x 2M)
其中M为集合的大小，M固定为0，一共有2M个状态，每个状态需要O(M + k) = O(M)的判断(k ≤ M)，总时间复杂度为O(M x 2M)。
空间复杂度：O(M)
即存放临时集合的控件代价。
三、总结
代码实现的过程中，用到了位运算，那么位运算是如何得到所有数的状态的呢？
比如说，对于某一个位置上的数字i以及二进制数mark，可以判断(1 << i) & mark 是否为 0，如果不为0则说明i在子集当中。
当然，9位二进制数i的范围是[0,8]，不是数字的[1,9]，就需要做一个映射。
