解题思路:从前往后遍历数组,每个元素有选择和不选择 2种状态。
1、选择第i个元素:此时组合结果为=原来的组合 U 原来每一个组合加上元素i 的组合, U表示并集 。
2、不选择第i个元素:此时组合结果不变。
设f(i)表示前i个元素的组合。初始条件 f(0) =[ [] ] ;
递推公式:
f(i) = f(i-1) U foreach(f(i-1)) { f(i-1) U s[i] } i>=1 U表示并集
代码如下:
import java.util.*; public class Solution { ArrayList<Integer> subResult = new ArrayList(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { // 升序排列 Arrays.sort(S); ArrayList<ArrayList<Integer>> result = new ArrayList(); ArrayList<Integer> subResult = new ArrayList(); // 一个都不选择 result.add(subResult); for(int i = 0 ; i< S.length; i++){ // 选择S[i]时,才会增加状态 原先的SubResult 每个增加一个S[i]; ArrayList<ArrayList<Integer>> newResult = new ArrayList(); for(ArrayList<Integer> lastSubResult : result){ ArrayList<Integer> newSubResult = new ArrayList(); newSubResult.addAll(lastSubResult); newSubResult.add(S[i]); newResult.add(newSubResult); } result.addAll(newResult); } return result; } }