这题个人理解为有两个点需要实现:
1.深度递归时需要做非递减的判断。这个好像到就使用 !path.isEmpty() && nums[i] < path.get(path.size() - 1)
这句判断就行。由于path中存放的是非递减的子序列,所以新加入的元素一定要不小于最后一个值。
2.宽度for循环遍历时的去重。由于有重复元素,在宽度遍历时需要过滤掉之前重复遍历的元素。之前的做法是if(i>start && nums[i]==nums[i-1]) continue;
,但是由于这次的数组并不可以进行排序所以,nums[i]==nums[i-1]
这个操作也就不行了。
最终解决方法是使用一个hash表来解决。可以是map,set,也可以是数组,因为nums数组中的值是有范围的 -100 <= nums[i] <= 100
剩下还有一些小细节,比如之前有return 操作,而这次不能return
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums,0);
return res;
}
private void backtracking (int[] nums, int start) {
if (path.size() > 1) {
res.add(new ArrayList<>(path));
}
int[] used = new int[201];
for (int i = start; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
(used[nums[i] + 100] == 1)) continue;
used[nums[i] + 100] = 1;
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
要满足两个条件:
1.全排列,序列大小要跟数组一样
2.不能重复添加元素 --两种解决办法 除了代码中的还可以用一个数组来标记该元素是否使用过。
class Solution {
private List<List<Integer>> result;
private List<Integer> list;
public List<List<Integer>> permute(int[] nums) {
result = new LinkedList<>();
list = new LinkedList<>();
backtracking(nums);
return result;
}
public void backtracking(int[] nums){
if(list.size() == nums.length){
result.add(new LinkedList<>(list));
return;
}
for(int i= 0 ;i<nums.length;i++){
if(list.contains(nums[i]) ) continue;
list.add(nums[i]);
backtracking(nums);
list.remove(list.size()-1);
}
}
}
现在有重复的数字
在上一题中不能重复添加元素,其实就是深度递归时的去重。由于上题有没有重复元素的限制所以不用考虑宽度for循环遍历时的去重。
这题去重则需要设计两个方向
1.宽度for循环时去重,重复元素不需要再求全排列,方法还是先对数组进行排序,然后使用i>0 && nums[i]==nums[i-1]
这个条件,但是光这样写还不够,你无法区分现在判断的是在尽显深度还是宽度,所以要加上&& used[i-1] ==0
,这个条件就是为了确定他是在宽度时的遍历。
2.深度去重,深度去重则和上题一样,只不过由于存在重复元素不能使用contains函数了,只能使用hash数组来进行标记。
class Solution {
private List<List<Integer>> result;
private List<Integer> list;
public List<List<Integer>> permuteUnique(int[] nums) {
result = new LinkedList<>();
list = new LinkedList<>();
int[] used = new int[nums.length];
Arrays.sort(nums);
backtraking(nums,used);
return result;
}
public void backtraking(int[] nums,int[] used){
if(list.size() == nums.length){
result.add(new LinkedList<>(list));
return ;
}
for(int i=0;i<nums.length;i++){
if(i>0 && nums[i]==nums[i-1] && used[i-1] ==0) continue;
if(used[i] !=0) continue;
list.add(nums[i]);
used[i] = 1;
backtraking(nums,used);
used[i] = 0;
list.remove(list.size()-1);
}
}
}