| DFS算法 | 您所在的位置：网站首页 › 集合的所有子集的算法 › DFS算法 |
DFS算法
|
目录1. 题目来源2. 普通方法1. 思路2. 代码3. 运行结果3. DFS算法1. 概念2. 解题思路3. 代码4. 运行结果4. 对比
1. 题目来源
牛客网，集合的所有子集(一)
https://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9
数学上排列组合中的组合，从N个元素的集合中拿出M(0≤ M ≤ N)个元素的可能数，标记为 这里具体在做的就是用遍历索引的方式取出想要的集合 比如数组为{1, 2, 3, 4, 5}，要取0个数，那么所有可能就是{}。1个集合 比如数组为{1, 2, 3, 4, 5}，要取1个数，那么所有可能就是{{1}, {2}, {3}, {4}, {5}}。5个集合 比如数组为{1, 2, 3, 4, 5}，要取2个数，那么所有可能就是{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}。10个集合 比如数组为{1, 2, 3, 4, 5}，要取3个数，那么所有可能就是{{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}}。10个集合 比如数组为{1, 2, 3, 4, 5}，要取4个数，那么所有可能就是{{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}}。5个集合 比如数组为{1, 2, 3, 4, 5}，要取5个数，那么所有可能就是{{1, 2, 3, 4, 5}}。1个集合 2. 代码 import java.util.ArrayList; /** * @className SolutionTest * @description * @author liwei * @date 2022/9/8 15:29 * @version V1.0 **/ public class SolutionTest { public static void main(String[] args) { int[] ints = {5, 4, 3, 2, 1}; System.out.println(subsets(ints)); } public static ArrayList subsets(int[] ints) { // 插入排序，升序排列 for (int i = 0, length = ints.length; i < length - 1; i++) { int tmpValue = ints[i]; int tmpIndex = i; for (int j = i + 1; j < ints.length; j++) { if (tmpValue > ints[j]) { tmpValue = ints[j]; tmpIndex = j; } } if (i != tmpIndex) { ints[tmpIndex] = ints[i]; ints[i] = tmpValue; } } ArrayList lists = new ArrayList(); // 循环，需要从数组中取i个数，然后取出i个数的所有可能。 // 比如数组为{1, 2, 3, 4, 5}，要取1个数，那么所有可能就是{{1}, {2}, {3}, {4}, {5}} // 比如数组为{1, 2, 3, 4, 5}，要取2个数，那么所有可能就是{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}} for (int number = 0; number * @author liwei * @date 2022/8/10 20:22 */ public static ArrayList subsets(int[] ints, int number) { ArrayList lists = new ArrayList(); // 特殊处理，如果需要的个数为0，那么直接添加一个空集合，然后返回 if (number ints[j]) { tmpValue = ints[j]; tmpIndex = j; } } if (i != tmpIndex) { ints[tmpIndex] = ints[i]; ints[i] = tmpValue; } } // 调用FDS return subsetsFDS(ints); } /** * @description FDS算法求解数组的所有子集合，包括空数组，内含递归 * @author liwei * @date 2022/9/9 11:47 * @param ints * 数组 * @return java.util.ArrayList **/ public static ArrayList subsetsFDS(int[] ints) { ArrayList arrayList = new ArrayList(); if (null == ints || ints.length |
。M从0开始遍历到N，就是所求的所有子集合。这里要结果不是数，而且取的元素集合。【本文地址】
公司简介
联系我们