方式一：利用二进制
举个例子：假设当前数组为 【1,2,3】
那么，用二进制表示就是：
000 : 一个元素都不取
001 ：取数组元素 3
010 ：取数组元素 2
011 ：取数组元素 2,3
100 ：取数组元素 1
101 ：取数组元素 1,3
110 ：取数组元素 1,2
111 ：取数组元素 1,2,3
也就是说，知道使用 for 循环从 0 开始遍历到 2^n - 1（Math.pow(2,nums.length) - 1 ）,然后利用位运算判断每个位置取或者不取即可。
代码实现
public void combination(int nums[]) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < Math.pow(2, nums.length); i++) {
int t = i;
for (int j = 0; j < nums.length; j++) {
//t == 0 表示什么都不取
if (t == 0) break;
//判断 t 的最后一位是否为 1
if ((t & 1) == 1) {
//加入倒数第 j 个元素
temp.add(nums[nums.length - 1 - j]);
}
t >>= 1;
}
System.out.println(Arrays.toString(temp.toArray()));
temp.clear();
}
}
运行结果
[]
[2]
[1]
[2, 1]
[0]
[2, 0]
[1, 0]
[2, 1, 0]
方法二： DFS
考虑当前位置，每个位置都有选和不选两种情况
public void combination2(int nums[], ArrayList<Integer> temp, int curIndex) {
if (curIndex == nums.length) {
System.out.println(Arrays.toString(temp.toArray()));
return;
}
//选
temp.add(nums[curIndex]);
combination2(nums, temp, curIndex + 1);
//退选
temp.remove(temp.size() - 1);
// 不选
combination2(nums, temp, curIndex + 1);
}
运行结果
[0, 1, 2]
[0, 1]
[0, 2]
[0]
[1, 2]
[1]
[2]
[]
