TODO: 78. 子集🔖递归

• https://leetcode-cn.com/problems/subsets/

问题描述

给定一个正整数n，生成集合 {1,2,3,…n} 的所有子集

问题思路

思路一：二进制法

利用二进制“是否显现”的转换思路来解决这个问题，一个数字在子集当中就标记为1反之标记为0，就比如 n=3 ，输出： {}{1,0,0}{0,1,0}{0,0,1}{1,1,0}{1,0,1}{0,1,1}{1,1,1}

代码思路

思路一：利用动态数组数据结构

输入的n就是动态数组的初始大小
然后依次利用“吞进来”和“吐出去”尾元素来实现

java代码实现

package com.wztlink1013.al._递归法_;
/*
 * 作用：测量代码运行时间
 */
import java.text.SimpleDateFormat;
import java.util.Date;
public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
    public interface Task {
        void execute();
    }
    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始：" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束：" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时：" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}

package com.wztlink1013.al._递归法_;
import java.util.ArrayList;
/**
 * 子集问题
 */
public class SubSetting {
    static ArrayList<Integer> x  = new ArrayList<Integer>();
    static int cnt = 0;
    public static void main(String args[]) {
        int n = 4;
        Times.test("当n = " + n + "时候的耗费时间", new Times.Task() {
            public void execute() {
                Subsetting(n);
            }
        });
    }
    private static void Subsetting(int n) {
        if (n > 0) {
            x.add(0);
            Subsetting(n - 1);
            x.remove(x.size() - 1);
            x.add(1);
            Subsetting(n - 1);
            x.remove(x.size() - 1);
        }else {
            OutputOneSubsetBinary();
            OutputOneSubset();
            System.out.print("\n");
        }
    }
    private static void OutputOneSubset() {
        System.out.printf("; {");
        int k = 0;
        for (int i = x.size() - 1; i >=0; i--) {
            if (x.get(i) == 1) {
                if (k > 0)
                    System.out.printf(",");
                System.out.printf("%d", x.size() - i);
                k++;
            }
        }
        System.out.printf("}");
    }
    private static void OutputOneSubsetBinary() {
        System.out.printf("%010d: ", ++cnt);
        for (int i = x.size() - 1; i >= 0; i--)
            System.out.printf("%d", x.get(i));
    }
}

运行结果：

n：18（分钟）

n：19（分钟）

n：20（分钟）

n：21（分钟）

n：22（分钟）

n：23（分钟）

网上查的代码！

class Main
{
    static void printSubsets(String[] set)
    {
        int n = set.length;
        for (int i = 0; i < (1<<n); i++)
        {
            System.out.print("{ ");
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) > 0)
                    System.out.print(set[j] + " ");
            System.out.println("}");
        }
    }
    public static void main(String[] args)
    {
        String[] set = {"1", "2", "3", "4",
                        "5", "6", "7", "8"};
        printSubsets(set);
    }
}