题目描述

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

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

示例:

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

输出:

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

解题思路

回溯法

设置一个头指针int first和一个当前列表ArrayList<Integer> curList，每次（递归地）进入回溯方法时，先将当前列表curList加入结果列表，再对数组从头指针first到尾部进行遍历，每次遍历都分三步：

在当前列表curList加入当前指针对应的数组的元素nums[i]
（递归地）处理剩下的i+1到nums.length - 1个元素
回溯，删掉刚才用过的元素（尾部元素）

Java 实现

public List<List<Integer>> subsets (int[] nums) {

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

    backtrack(0,new ArrayList<>(),ans,nums);

    return ans;

}

private void backtrack (int first, ArrayList<Integer> curList, List<List<Integer>> ans,int[] nums) {

    ans.add(new ArrayList<Integer>(curList));

    for (int i = first; i < nums.length;i++) {

        curList.add(nums[i]);

        backtrack(i+1,curList,ans,nums);

        curList.remove(curList.size()-1); // 回溯，删掉用过的元素

    }

}

心得体会

这一题有点像第17题-电话号码的字母组合，回溯算法都体现在处理完一次递归后，要将刚才用过的尾部元素删掉，不同之处在于，这一题不需要在达到固定长度时将当前列表加入结果列表，而是每次进入回溯方法时，都加一次。

巴特西

【LeetCode】78-子集

题目描述

解题思路

回溯法

Java 实现

心得体会

最新文章

热门文章