集合的所有子集(二)

import java.util.*;


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

    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        // write code here
        // 回溯
        Arrays.sort(nums);
        backtracing(0, nums);
        return res;
    }

    private void backtracing(int start, int[] nums) {
        res.add(new ArrayList<>(path));

        for(int i = start; i < nums.length; i++) {
            // 层内去重
            if((i != start) && (nums[i] == nums[i - 1])) continue;
            path.add(nums[i]);
            backtracing(i + 1, nums);
            path.remove(path.size() - 1);
        }
    }
}

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();
        }
    }
}

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());
        }
    }
}

package main
import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型二维数组
*/
func subsets( nums []int ) [][]int {
    sort.Ints(nums)
    ans:=[][]int{}
    var dfs func([]int,int)
    dfs=func(path []int,idx int){
        tmp:=make([]int,len(path))
        copy(tmp,path)
        ans=append(ans,tmp)
        for i:=idx;i<len(nums);i++{
            if i>idx&&nums[i]==nums[i-1]{
                continue
            }
            path=append(path,nums[i])
            dfs(path,i+1)
            path=path[:len(path)-1]
        }
    }
    dfs([]int{},0)
    return ans
}

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型二维数组
#
class Solution:
    """
    题目：
        集合的所有子集(二)
        https://www.nowcoder.com/practice/a3dfd4bc8ae74fad9bc65d5ced7ae813?tpId=117&&tqId=39446&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
    参考：
        大神：代码界的小白
        https://leetcode.cn/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/
    算法：
        题目要求：寻找nums的所有子集，结果按字典序排序
        1. 对nums进行排序
        2. 定义回溯函数dfs(combine, idx)，初始combine为[]，idx为0。
            a. 记录子集combine
            b. 枚举可选元素，加入combine，从下一个下标继续搜索；搜索完毕，回溯
    复杂度：
        时间复杂度：O(nlogn + n * 2^n) = O(n * 2^n)，排序算法的复杂度：O(nlogn)，构造子集：共2^n种状态，每种状态需要O(n)复杂度构造子集，构造子集的总复杂度为O(n * 2^n)
        空间复杂度：O(n)，临时数组combine
    """

    def subsets(self, nums):
        # write code here
        def dfs(combine, idx):
            res.append(combine[:])
            for i in range(idx, n):
                if i > idx and nums[i] == nums[i - 1]: # 剪枝：前一个相同的数已经回溯了
                    continue
                combine.append(nums[i])
                dfs(combine, i + 1)
                combine.pop()

        nums.sort()
        res, n = [], len(nums)

        dfs([], 0)

        return res


if __name__ == '__main__':
    s = Solution()

    # nums = [1, 2]

    # nums = [1]

    nums = [1, 1, 1]

    # nums = [3, 6, 7, 5]

    res = s.subsets(nums)

    print res

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型二维数组
 */
let result=[],path=[],visited=[];
function subsets( nums ) {
    // write code here
    nums.sort(function(a,b){
        return a-b;
    })
    backTrace(nums,nums.length,0);
    return result;
}
function backTrace(n,k,start){
    result.push([...path]);
    for(let i=start;i<k;i++){
        // 增加访问标记visited，避免[1,1,1] 重复元素重复添加
        if(i>start && n[i]==n[i-1]) continue; // 满足条件继续
        // if(i > 0 && n[i]==n[i-1] && !visited[i-1]) continue;
        path.push(n[i]);
       // visited[i]=1; // 节点被访问
        backTrace(n,k,i+1);
        path.pop();
       // visited[i]=0; // 节点访问标记置0
    }
}
module.exports = {
    subsets : subsets
};

class Solution:
    def subsets(self , nums: List[int]) -> List[List[int]]:
        # write code here
        if len(nums)<=1:
            return [nums]
        res=[]
        nums.sort()
        def backtrace(start,path):
            res.append(path)
            add=set()
            for i in range(start,len(nums)):
                if nums[i] not in add:
                    add.add(nums[i])
                    cur_path=path+[nums[i]]
                    backtrace(1+i, cur_path)
        backtrace(0,[])
        #res.sort()
        return res

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);
        }
    }
}