90. 子集 II
2023-12-14 17:31:55
原题链接:
https://leetcode.cn/problems/subsets-ii/description/
完成情况:
解题思路:
/**
* 包含重复元素,但不包含重复解集。
*
* @param nums
* @return
*/
public List<List> subsetsWithDup(int[] nums) {
//输入:nums = [1,2,2]
//输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
// TODO 方法一:永远记住有个暴力的Set去重
//作为单独元素回溯时,同一个元素不能出现两次
if (i>startUsedIndex && nums[i-1] == nums[i]){
continue;
}
参考代码:
package 代码随想录.回溯;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class _90子集II {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> listSubsets = new ArrayList<Integer>();
/**
* 包含重复元素,但不包含重复解集。
*
* @param nums
* @return
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {
//输入:nums = [1,2,2]
//输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
// TODO 方法一:永远记住有个暴力的Set去重
//作为单独元素回溯时,同一个元素不能出现两次
Arrays.sort(nums);
backTrack(nums,0); //想一下终止条件是啥?不像前面还有分隔逗号判断,这个只有长度判断
return result;
}
/**
*
* @param nums
* @param startUsedIndex
*/
private void backTrack(int[] nums, int startUsedIndex) {
//这道题空集也算,部分也算,所以直接添加
result.add(new ArrayList<>(listSubsets));
// if (startUsedIndex == nums.length - 1) {
// return;
// }
//里面就得采取剪枝
for (int i = startUsedIndex;i< nums.length;i++){
// 跳过当前树层使用过的、相同的元素
//如果这里不加判断则直接使用了
if (i>startUsedIndex && nums[i-1] == nums[i]){
continue;
}
listSubsets.add(nums[i]);
backTrack(nums,i+1);
listSubsets.remove(listSubsets.size()-1);
}
}
}
错误经验吸取
文章来源:https://blog.csdn.net/weixin_43554580/article/details/134871411
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!