LeetCode0078.子集

78.子集

描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

**说明：**解集不能包含重复的子集。

实例

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题解

全排列问题

• 维护一个栈用于保存迭代时的状态
• 栈中使用int[]描述一个状态
• 递归调用
• 其中，index表示当前考虑哪一个位置元素的不同情况
• 其中，结尾处的state.pop()用于保证当前状态被移除

public static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> linkedLists = new LinkedList<>();

    getAllPoss(nums,0,new Stack<int[]>(),linkedLists);

    return linkedLists;
}

public static void getAllPoss(int[] nums, int index,Stack<int[]> state, List<List<Integer>> linkedLists){
    int[] nowState;
    int[] lastState;

    if (index == nums.length){
        //添加结果到LinkedLists
        lastState = state.pop();
        List<Integer> nowList = new LinkedList<>();
        for (int i = 0; i < lastState.length; i++) {
            if (lastState[i] == 1)
                nowList.add(nums[i]);
        }
        linkedLists.add(nowList);
        return;
    }



    if (state.empty()){
        nowState = new int[nums.length];
    } else {
        lastState = state.pop();
        state.push(lastState);
        nowState = lastState.clone();
    }

    nowState[index] = 1;
    state.push(nowState);
    getAllPoss(nums,index+1,state,linkedLists);

    nowState[index] = -1;
    state.push(nowState);
    getAllPoss(nums,index+1,state,linkedLists);

    if (!state.empty())
        state.pop();


}