leetcode — subsets-ii

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/**

 * Source : https://oj.leetcode.com/problems/subsets-ii/

 *

 *

 * Given a collection of integers that might contain duplicates, S, return all possible subsets.

 *

 * Note:

 *

 * Elements in a subset must be in non-descending order.

 * The solution set must not contain duplicate subsets.

 *

 * For example,

 * If S = [1,2,2], a solution is:

 *

 * [

 *   [2],

 *   [1],

 *   [1,2,2],

 *   [2,2],

 *   [1,2],

 *   []

 * ]

 *

 */

public class SubSet2 {

    private List<List<Integer>> result = null;

    /**

     *

     *

     * @return

     */

    public List<List<Integer>> subset (int[] arr) {

        result = new ArrayList<List<Integer>>();

        List<Integer> set = new ArrayList<Integer>();

        Arrays.sort(arr);

        recursion(arr, 0, set);

        return result;

    }

    private void recursion (int[] arr, int index, List<Integer> set) {

        if (index == arr.length) {

            return;

        }

        // 初始化上一次出栈的元素为当前将要进栈的元素-1，为了不和将要进栈的元素相同

        int last = arr[index]-1;

        for (int i = index; i < arr.length; i++) {

            // 如果上一次出栈的元素等于准备进栈的元素，则说明两个元素一样，跳过

            if (last == arr[i]) {

                continue;

            }

            set.add(arr[i]);

            List<Integer> temp = new ArrayList<Integer>(set);

            result.add(temp);

            recursion(arr, i + 1, set);

            last = set.remove(set.size()-1);

        }

    }

    private static void print (List<List<Integer>> list) {

        for (List<Integer> arr : list) {

            System.out.println(Arrays.toString(arr.toArray(new Integer[arr.size()])));

        }

        System.out.println();

    }

    public static void main(String[] args) {

        SubSet2 subSet2 = new SubSet2();

        int[] arr = new int[]{1,2,2};

        int[] arr1 = new int[]{1,2,3,3,3,3,4};

        print(subSet2.subset(arr));

        print(subSet2.subset(arr1));

    }

}
巴特西

leetcode — subsets-ii

最新文章

热门文章
