leetcode 90. Subsets II and 78

2017-11-02  本文已影响0人  哲哲哥

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

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


首先写一个如果没有重复数字的组合,该怎么写?
可以这样考虑对与1,2,3。我们可以第一次去1,2,3然后回退到2这一层把3标注不取1,2。再到1这一层标注2不取1,3然后到1这一层1。有时我们标注一个数是“取还是不取”,使用下标idx不好标注时,我们可以考虑使用 boolean[] v 数组来标注

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CopyOfSolution90 {

    public static List<List<Integer>> ans = new LinkedList<List<Integer>>();
    public static LinkedList<Integer> list = new LinkedList<Integer>();
    public static boolean[] v = new boolean[100];
 
    public static void robot(int idx, int[] nums) {
        if (idx >= nums.length) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (v[i]) {
                    temp.add(nums[i]);
                }
            }
            System.out.println(temp);
            ans.add(temp);
            return;

        }
        
            v[idx] = true;//取
            robot(idx + 1, nums);
            v[idx] = false;//不取
            robot(idx + 1, nums);
        
    }

    public static void main(String[] args) {
        int arr[] = {1,2,3};
        robot(0, arr);
        // System.out.println(ans);
    }

}

在考虑如果有重复数字,如果这一层的数字和上一层的数字相同,但是上一层的数字没有取,那么这一层的数字也不能取

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution90 {

    public static List<List<Integer>> ans = new LinkedList<List<Integer>>();
    public static LinkedList<Integer> list = new LinkedList<Integer>();
    public static boolean[] v = new boolean[100];

    public static void robot(int idx, int[] nums) {
        if (idx >= nums.length) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                if (v[i]) {
                    temp.add(nums[i]);
                }
            }
            System.out.println(temp);
            ans.add(temp);
            return;

        }
        if (idx > 0 && nums[idx - 1] == nums[idx] && v[idx - 1] == false) {
            v[idx] = false;
            robot(idx + 1, nums);//上次没有取说明下一次想取到一个不同的数
        } else {
            v[idx] = true;//取
            robot(idx + 1, nums);
            v[idx] = false;//不取
            robot(idx + 1, nums);
        }
    }

    public static void main(String[] args) {
        int arr[] = {1,2,2};
        robot(0, arr);
        // System.out.println(ans);
    }

}

上一篇下一篇

猜你喜欢

热点阅读