有哪些可以接单做任务的网站,免费商城网站申请,金沙洲网站建设工作室,百度推广开户代理商题目
输入一个不含重复数字的数据集合#xff0c;请找出它的所有子集。例如#xff0c;数据集合[1#xff0c;2]有4个子集#xff0c;分别是[]、[1]、[2]和[1#xff0c;2]。
分析
如果集合中包含n个元素#xff0c;那么生成子集可以分为n步#xff0c;每一步从集合中…题目
输入一个不含重复数字的数据集合请找出它的所有子集。例如数据集合[12]有4个子集分别是[]、[1]、[2]和[12]。
分析
如果集合中包含n个元素那么生成子集可以分为n步每一步从集合中取出一个数字此时面临两个选择将该数字添加到子集中或不将该数字添加到子集中。生成一个子集可以分为若干步并且每一步都面临若干选择这正是应用回溯法的典型场景。 适用回溯法的问题的一个特征是问题可能有很多个解并且题目要求列出所有的解。如果题目只是要求计算解的数目或者只需要求一个最优解通常是最大值或最小值那么可能需要运用动态规划。
解
public class Test {public static void main(String[] args) {int[] nums {1, 2};ListListInteger result subsets(nums);for (ListInteger item : result) {System.out.println(item);}}public static ListListInteger subsets(int[] nums) {ListListInteger result new LinkedList();if (nums.length 0) {return result;}helper(nums, 0, new LinkedListInteger(), result);return result;}private static void helper(int[] nums, int index, LinkedListInteger subset, ListListInteger result) {if (index nums.length) {result.add(new LinkedList(subset));}else if (index nums.length) {helper(nums, index 1, subset, result);// 直接不添加元素subset.add(nums[index]);// 添加元素helper(nums, index 1, subset, result);// 等递归函数执行完成之后函数helper也执行完成接下来将回到前一个数字的函数调用处继续执行。那么此时将回溯到父节点以便尝试父节点的其他选项。// 在回溯到父节点之前应该清除已经对子集状态进行的修改。此前在子集subset中添加了一个数字此时应该将它删除。subset.removeLast();}}
}
