Subsets

1. 问题描述

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

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

2. 求解

递归法

这道题类似于数组的组合问题,可以用递归法求解。N个数中每个数都分为要与不要两种情况,求解的过程如下图。递归的边界条件为N个数都遍历完了。

public class Solution {
    public static List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets(int[] nums) {
        result.clear();
        result.add(new ArrayList<Integer>());
        combination(nums, 0, new ArrayList<Integer>());
        return result;
    }

    public void combination(int[] nums, int index, List<Integer> list) {
        if(index == nums.length) {
            return;
        }
        combination(nums, index + 1, new ArrayList<Integer>(list));
        list.add(nums[index]);
        result.add(list);
        combination(nums, index + 1, new ArrayList<Integer>(list));
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券