Dado un conjunto de enteros distintos, S, devuelve todos los subconjuntos posibles.
Nota: 1) Los elementos de un subconjunto deben estar en orden no descendente. 2) El conjunto de soluciones no debe contener subconjuntos duplicados.
For example, given S = [1,2,3], the method returns: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Pensamientos
Dado un conjunto S de n enteros distintos, existe una relación entre Sn y Sn-1. El subconjunto de Sn-1 es la unión de {subconjunto de Sn-1} y {cada elemento en Sn-1 + un elemento más}. Por lo tanto, una solución Java se puede formalizar rápidamente.
Solución Java
public ArrayList<ArrayList<Integer>> subsets(int[] S) { if (S == null) return null; Arrays.sort(S); ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < S.length; i++) { ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>(); //get sets that are already in result for (ArrayList<Integer> a : result) { temp.add(new ArrayList<Integer>(a)); } //add S[i] to existing sets for (ArrayList<Integer> a : temp) { a.add(S[i]); } //add S[i] only as a set ArrayList<Integer> single = new ArrayList<Integer>(); single.add(S[i]); temp.add(single); result.addAll(temp); } //add empty set result.add(new ArrayList<Integer>()); return result; } |
