每日一省之———— 递归 + 回溯求集合的幂集

本文主要是介绍每日一省之———— 递归 + 回溯求集合的幂集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法求解过程示意图


import java.util.ArrayList;
import java.util.List;/*** 所谓幂集（Power Set）， 就是一个集合中所有的子集（包括全集和空集）作为元素构成的集合。* * 该类通过遍历一棵满二叉树，求解集合的幂集。程序的原理是：把求幂集元素的过程看作是在先序遍历一棵深度为n+1的满二叉树，* 从根节点开始，访问左孩子表示幂集元素（集合的子集）中包含集合的第一个元素，访问右孩子表示幂集元素中不包含集合的* 第一个元素，这样，在二叉树的第二层完成了对集合第一个元素的取舍，依次类推，当遍历到达第n+1层，也就是二叉树的叶* 子节点时，完成了集合所有元素的取舍，这时输出一个取舍后的幂集元素。满二叉树的第n+1层共有2n个叶子节点，代表了集* 合的2n个幂集元素，待遍历输出完整棵满二叉树的叶子节点，也就得到了我们要求的幂集。*/
public class PowerSetFinder<V>
{public static void main(String[] args){// 初始化一个集合，放在list里面List<String> list = new ArrayList<String>();list.add("A");list.add("B");list.add("C");list.add("D");List<String> li = new ArrayList<String>();printPowerSet(0, list, li);System.out.println();System.out.println("-------------------------------------------------");System.out.println();List<Integer> list1 = new ArrayList<Integer>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);List<Integer> li1 = new ArrayList<Integer>();printPowerSet(0, list1, li1);}/*** 递归 + 回溯 求幂集* @param i* @param list* @param li* @author lhever 2017年2月21日 下午11:50:21* @since v1.0*/public static <V> void  printPowerSet(int i, List<V> list, List<V> li){if (i > (list.size() - 1)){System.out.println(li);} else{li.add(list.get(i));// 左加printPowerSet(i + 1, list, li); // 递归方法li.remove(list.get(i)); // 右去printPowerSet(i + 1, list, li);}}}