Leetcode算法Java全解答--78. 子集

- 日理万妓 2022-04-03 01:28 151阅读 0赞

# Leetcode算法Java全解答–78. 子集 #

### 文章目录 ###

*  Leetcode算法Java全解答--78. 子集
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

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

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

## 想法 ##

和077差不多，  
回溯算法： (后面的数据是用下标表示)以1起始数据，然后将2.3.4拼进去；  
再回头以2为起始位置，这时候就不能把1算进去，然后把3.4拼进去

## 结果 ##

超过50%的测试案例

时间复杂度/空间复杂度：n/n

## 总结 ##

## 代码 ##

### 我的答案 ###

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
    
        List<Integer> cur = new ArrayList<>();
    
        dfs(nums, 0, cur, ans);
        return ans;
    }
    
    private void dfs(int[] nums, int last, List<Integer> cur, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(cur));
        for (int i = last; i < nums.length; i++) {
            cur.add(nums[i]);
            dfs(nums, i + 1, cur, ans);
            cur.remove(cur.size() - 1);
        }
        System.out.println(ans.toString());
    }

### 大佬们的答案 ###

public List<List<Integer>> better(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
    
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                int num = nums[i];
                List<Integer> one = new ArrayList<>();
                one.add(num);
                result.add(one);
                int resultSize = result.size();
                for (int j = 0; j < resultSize - 1; j++) {
                    List<Integer> newone = new ArrayList<>();
                    newone.addAll(result.get(j));
                    newone.add(num);
                    result.add(newone);
                }
            }
            result.add(new ArrayList<>());
            return result;
        }

### 测试用例 ###

@Test
        public void test078() {
            // 创建测试案例
            int[] nums1 = new int[] { 1, 2, 3 };
    
            // 测试案例期望值
            List<List<Integer>> expResult1 = new ArrayList<>();
            List<Integer> list1 = new ArrayList<>();
            list1.add(1);
            List<Integer> list2 = new ArrayList<>();
            list2.add(2);
            List<Integer> list3 = new ArrayList<>();
            list3.add(3);
            List<Integer> list4 = new ArrayList<>();
            list4.add(1);
            list4.add(2);
            List<Integer> list5 = new ArrayList<>();
            list5.add(1);
            list5.add(3);
            List<Integer> list6 = new ArrayList<>();
            list6.add(2);
            list6.add(3);
            List<Integer> list7 = new ArrayList<>();
            list7.add(1);
            list7.add(2);
            list7.add(3);
            List<Integer> list8 = new ArrayList<>();
            expResult1.add(list1);
            expResult1.add(list2);
            expResult1.add(list3);
            expResult1.add(list4);
            expResult1.add(list5);
            expResult1.add(list6);
            expResult1.add(list7);
            expResult1.add(list8);
    
            // 执行方法
            Solution078 solution078 = new Solution078();
            List<List<Integer>> result1 = solution078.subsets(nums1);
    
            // 判断期望值与实际值
            Assert.assertEquals(expResult1, result1);
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan