Leetcode分类——递归、回溯、分治
- 递归与回溯的区别
- Leetcode 78
- Leetcode 90
递归与回溯的区别
回溯是一种应用递归算法，递归不是
Leetcode 78
题目 循环的困难之处在于不好模拟选不选某一个数的过程，即选了一个数，不方便回溯到不选这个数的情况。
代码语言：javascript复制给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]解法一：回溯法
代码语言：javascript复制class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList();//存放结果
List<Integer> temp = new ArrayList<>();//存放一次完整递归的结果
//递归放入
addElem(nums, 0, temp, list);
return list;
}
private void addElem(int[] nums, int n, List<Integer> temp, List<List<Integer>> list) {
//递归的出口
if (n >= nums.length) {
List addTemp = new ArrayList(temp);
list.add(addTemp);
//list.add(temp);//关键：如果直接放入temp，则所有结果都等于最后一次放入的情况
return;
}
//放入该元素
temp.add(nums[n]);
addElem(nums, n 1, temp, list);
//回溯，不放入该元素
temp.remove(temp.size() - 1);
addElem(nums, n 1, temp, list);
}
}方法二：位运算 位运算介绍：
- & 按位与
- | 按位或
- ^ 按位异或：相同为0，不同为1
- ~ 取反
- << 左移：乘以2
- >> 右移：除以2
这里的集合有三个元素A、B、C，则三个元素共有2^3=8种组成集合的方式，于是可以用0（000）~7（111）来表示这些集合。
集合 | 整数 | A | B | C |
|---|---|---|---|---|
{} | 000=0 | 0 | 0 | 0 |
{C} | 001=1 | 0 | 0 | 1 |
{B} | 010=2 | 0 | 1 | 0 |
{B,C} | 011=3 | 0 | 1 | 1 |
{A} | 100=4 | 1 | 0 | 0 |
{A,C} | 101=5 | 1 | 0 | 1 |
{A,B} | 110=6 | 1 | 1 | 0 |
{A,B,C} | 111=7 | 1 | 1 | 1 |
A元素为100=4，B元素为010=2，C元素为001=1。如需判断一个集合是否含有该元素，将这个集合的二进制表示与该元素的二进制表示做**&运算**，结果为真时，表示包含该元素，将其push进集合内。
代码语言：javascript复制9-1000000000
8-0100000000
7-0010000000
6-0001000000
5-0000100000
4-0000010000
3-0000001000
2-0000000100
1-0000000010
0-0000000001
9 8 7 6 5 4 3 2 1
组合共有2^10 = 1024种Leetcode 90
题目 利用set将list中相同的list剔除。
代码语言：javascript复制class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList();
List<Integer> temp = new ArrayList<>();
//需要对输入事先排序，使得得到的重复list顺序相同，能够被set认为是重复项
Arrays.sort(nums);
addElem(nums, 0, temp, list);
//将list<list>存为set<list>类型去重，最后转换为list
return new ArrayList<>(new HashSet<>(list));
}
private void addElem(int[] nums, int n, List<Integer> temp, List<List<Integer>> list) {
if (n >= nums.length) {
List addTemp = new ArrayList(temp);
list.add(addTemp);
return;
}
temp.add(nums[n]);
addElem(nums, n 1, temp, list);
temp.remove(temp.size() - 1);
addElem(nums, n 1, temp, list);
}
}
