集合的所有子集(二)

[编程题]集合的所有子集(二)

热度指数：3105 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组 nums ，其中可能包含重复元素，请你返回这个数组的所有可能子集。

返回的答案中不能包含重复的子集，将答案按字典序进行排序。

数据范围：数组长度满足 $1 \le nums \le 10 \$ ，数组中元素大小满足 $|val| \le 10 \$

示例1

输入

[1,2]

输出

[[],[1],[1,2],[2]]

示例2

输入

[1]

输出

[[],[1]]

算法知识视频讲解

Java

矜持的微笑

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
     ArrayList<ArrayList<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        // write code here
        Arrays.sort(nums);
        backtracking(nums,0);
        return result;
    }
    void backtracking(int[] nums,int start){
        result.add(new ArrayList<>(path));
        for(int i=start;i<nums.length;i++){
            if(i>start&&nums[i-1]==nums[i])continue;
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.removeLast();
        }
    }
}

编辑于 2024-01-29 15:44:28 回复(0)

Java

小螺号嘎嘎嘎

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    private ArrayList<ArrayList<Integer>>  result = new ArrayList<>();
    private Deque<Integer> path = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        Arrays.sort(nums);

        boolean[] used = new boolean[nums.length];
        backTracking(nums, 0, used);
        Collections.sort(result, new CustomComparator());
        return result;
    }

    private void backTracking(int[] nums, int index, boolean[] used) {
        result.add(new ArrayList<>(path));

        for (int i=index; i<nums.length; i++) {
            if (i > 0 && used[i-1] == false && nums[i] == nums[i-1]) continue;
            
            used[i] = true;
            path.offer(nums[i]);
            backTracking(nums, i+1, used);
            path.pollLast();
            used[i] = false;
        }
    }

    private static class CustomComparator implements Comparator<ArrayList<Integer>> {
        public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
            //if (a.isEmpty()) return 1;
            //if (b.isEmpty()) return -1;

            StringBuilder str1 = new StringBuilder();
            StringBuilder str2 = new StringBuilder();
            for (int e: a) str1.append(e);
            for (int e: b) str2.append(e);

            return str1.toString().compareTo(str2.toString());
        }
    }
}

发表于 2023-08-26 11:57:44 回复(0)

Java

刻苦的大熊猫在度假

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    //HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        //ans.add(list);
        Arrays.sort(nums);
        dfs(nums, 0, list);
        return ans;
    }
    
    public void dfs(int[] nums, int start, ArrayList<Integer> list){
        if(!ans.contains(list)){
            ans.add(new ArrayList<Integer>(list));
        }
        for(int i=start;i<nums.length;i++){
            list.add(nums[i]);
            dfs(nums, i+1, list);
            list.remove(list.size()-1);
        }
    }
}

发表于 2021-12-07 10:49:19 回复(0)

Java

合肥吴彦祖

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    List<Integer> list = new LinkedList<>();
    
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        // write code here
        Arrays.sort(nums);
        dfs(nums,0);
        return ans;
    }
    void dfs(int[] nums, int index){
        
        ans.add(new ArrayList(list));
        
        for(int i =index; i < nums.length; i++){
            if(i > index && nums[i] == nums [i-1]) {
                continue;
            }
            list.add(nums[i]);
            dfs(nums,i+1);
            list.remove(list.size() - 1);
        }
    }
}

发表于 2021-12-03 20:16:40 回复(0)