leetcode 78.Subsets&&90.SubsetsII

2017-07-30

Subsets

题目意思

给定一个整数数组，求其所有的子集
比如[1,2,3]所有子集为[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

经典的回溯算法

采用了递归框架实现，更加利于理解

public static List<List<Integer>> result = new ArrayList<>();
 public List<List<Integer>> subsets(int[] nums) {
        result.clear();
        result.add(new ArrayList<Integer>());
        int visited[] = new int[nums.length];
        int n = nums.length;
        backtracking(0,n,visited,nums);
        return result;
    }
    public void backtracking(int i,int n,int visited[],int[] nums){
        if(i>=n){
            return ;
        }
        visited[i] = 1;
        List<Integer> item = new ArrayList<>();
        for(int j=0;j<=i;j++){
            if(visited[j]==1)
                item.add(nums[j]);
        }
        if(item.size()>0)
            result.add(item);

        backtracking(i+1,n,visited,nums);
        visited[i] = 0;
        backtracking(i+1,n,visited,nums);
    }

SubsetsII

题目意思

输入一个整形数组，该数组可能存在重复的数字。返回得到这个数组的所有子集，比如输入[1,2,2]，返回[[],[1],[1,2],[1,2,2],[2],[2,2]]

和上个求子集题目不同的是这里可能含有相同的串

public class SubSetsII {
    public static List<List<Integer>> result = new ArrayList<>();
    public static void main(String[]args){
        result = new SubSetsII().subsetsWithDup(new int[]{1,4,4,4,4});
        for(int i=0;i<result.size();i++){
            System.out.print("[");
            for(int j=0;j<result.get(i).size();j++){
                System.out.print(result.get(i).get(j)+",");
            }
            System.out.print("]，");

        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        result.clear();
        result.add(new ArrayList<Integer>());
        int visited[] = new int[nums.length];
        int n = nums.length;
        backtracking(0,n,visited,nums);
        return result;
    }
    public void backtracking(int i,int n,int visited[],int[] nums){
        if(i>=n){
            return ;
        }
        visited[i] = 1;
        List<Integer> item = new ArrayList<>();
        for(int j=0;j<=i;j++){
            if(visited[j]==1)
                item.add(nums[j]);
        }
        if(item.size()>0) {
            boolean flag = true;
            for(int k = 1;k<result.size();k++){
                if(result.get(k).size()==item.size()){
                    for(int m=0;m<item.size();m++){
                        if(item.get(m).intValue()!=result.get(k).get(m).intValue()){
                            break;
                        }else {
                            if (m==item.size()-1)
                                flag = false;
                        }
                    }
                }
                if(!flag)
                    break;
            }
            if(flag)
            result.add(item);
        }

        backtracking(i+1,n,visited,nums);
        visited[i] = 0;
        backtracking(i+1,n,visited,nums);
    }
}

以上是我写的代码，实在求子集I中加了个判断重复结果的逻辑，就得到了。

大神代码

下面是看网上大神写的代码。

public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        sets(nums, 0, new ArrayList<Integer>(), result);
        return result;
    }

    private void sets(int[] nums, int start, ArrayList<Integer> path, List<List<Integer>> result) {
        if (start >= nums.length) {
            List<Integer> res = new ArrayList<>();
            res.addAll(path);
            result.add(res);
            return;
        }
        int cnt = 0;
        int curNum = nums[start];
        for (int i = start; i < nums.length; i++) {
            if (nums[i] == curNum) cnt++;
        }
        // without current number
        sets(nums, start + cnt, path, result);
        for (int i = 0; i < cnt; i++) {
            path.add(curNum);
            sets(nums, start + cnt, path, result);
        }
        for (int i = 0; i < cnt; i++) path.remove(path.size() - 1);
    }


public List<List<Integer>> subsetsWithDup(int[] nums) {
    Set<List<Integer>> result = new HashSet<List<Integer>>();
    List<Integer> empty = new ArrayList<Integer>();
    result.add(empty);
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        Set<List<Integer>> toAdd = new HashSet<List<Integer>>();
        for (List<Integer> list : result) {
            List<Integer> newList = new ArrayList<Integer>(list);
            newList.add(nums[i]);
            toAdd.add(newList);
        }
        result.addAll(toAdd);
    }
    return new ArrayList<List<Integer>>(result);
}

这个大神直接两套循环解决，解决思路我用结果状态集来展示
假设输入的是[1,2,2]

[[]]->>[[] 1]: 遍历第一遍 [[] 1]->>[[] 1 2 [1 2]]: 遍历第二遍 [[] 1 2 [1 2]]->>[[] 1 2 [2 2] [1 2] [1 2 2]]:遍历第三遍{"theme":"simple"}