题解 | #集合的所有子集#【Java】DFS / 回溯法
集合的所有子集
http://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9
思路:每个数字在子集中有两种情况,一种是不包含自己,另一种是包含自己。因此,可通过回溯法来记录每个数字分别在这两种情况下的组合。
import java.util.*; public class Solution { int length; ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> record = new ArrayList<>(); public ArrayList<ArrayList<Integer>> subsets(int[] S) { length = S.length; dfs(S, 0); return res; } private void dfs(int[] s, int position) { // 当前位置的索引越过数组的索引,则将子集添加到结果集合中 if (position > length - 1) { res.add(new ArrayList<>(record)); return; } // 子集不包含当前的数字 dfs(s, position + 1); // 子集包含当前的数字 record.add(s[position]); dfs(s, position + 1); // 复原回溯 record.remove(record.size() - 1); } }