LeetCode：78. Subsets（找出一个数组中所有的子集）

灰太狼 2022-04-08 08:57 173阅读 0赞

Given a set of **distinct** integers, *nums*, return all possible subsets (the power set).

**Note:** The solution set must not contain duplicate subsets.

**Example:**

Input: nums = [1,2,3]
    Output:
    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

--------------------

方法1：递归的方式

package leetcode;
    
    import org.junit.Test;
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author zhangyu
     * @version V1.0
     * @ClassName: Subsets
     * @Description: TOTO
     **/
    
    // 这种利用递归的方式
    public class Subsets2 {
        @Test
        public void fun() {
            int[] nums = {1, 2, 3};
            List<List<Integer>> list = subsets(nums);
            System.out.println(list);
        }
    
        private List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            List<Integer> subList = new ArrayList<>();
            subsets(nums, 0, subList, list);
            return  list;
        }
    
        private void subsets(int[] nums, int i, List<Integer> subList, List<List<Integer>> list){
            if (i == nums.length) {
                list.add(subList);
                return;
            }
            int num = nums[i];
            List<Integer> temp = new ArrayList<>(subList);
            temp.add(num);
            subsets(nums, i+1, temp, list);
            subsets(nums, i+1, subList, list);
            return;
        }
    }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

方法2：（利用非递归的方式，这种方法比较难以理解）

package leetcode;
    
    import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author zhangyu
     * @version V1.0
     * @ClassName: Subsets
     * @Description: TOTO
     * @date 2018/12/7 11:36
     **/
    
    // 找出一个数组中所有的子串
    public class Subsets3 {
        @Test
        public void fun() {
            int[] nums = {1, 2};
            List<List<Integer>> list = subsets(nums);
            System.out.println(list);
        }
    
        private List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            // 数组长度为0就直接返回
            if (nums == null || nums.length == 0) {
                return ret;
            }
            // 定义另外一个辅助数组
            int[] pos = new int[nums.length];
            int index = 0; //标志位index
            pos[0] = -1; //第一个位置为-1
            // 控制进行回溯
            while (index >= 0) {
                pos[index]++;
                if (pos[index] < nums.length) {
                    List<Integer> s = new ArrayList<Integer>();
                    for (int ii = 0; ii <= index; ii++) {
                        s.add(nums[pos[ii]]);
                    }
                    ret.add(s);
                    if (index < nums.length - 1) {
                        index++;
                        pos[index] = pos[index - 1];
                    }
                    continue;
                }
                index--;
            }
            ret.add(new ArrayList<Integer>());
            return ret;
        }
    }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

源码github地址：[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode