首页 > 代码库 > Subsets
Subsets
题目
Given a set of distinct integers, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S =[1,2,3]
, a solution is:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
方法一
使用DFS进行遍历。public void getSets(int[] S, int start, int end, List<List<Integer>> list, List<Integer> subList) { list.add(subList); for (int i = start; i < end; i++) { List<Integer> newSubList = new ArrayList<Integer>(subList); newSubList.add(S[i]); getSets(S, i + 1, end, list, newSubList); } } public List<List<Integer>> subsets(int[] S) { Arrays.sort(S); List<List<Integer>> list = new ArrayList<List<Integer>>(); List<Integer> subList = new ArrayList<Integer>(); getSets(S, 0, S.length, list, subList); return list; }
方法二
利用n和n-1之间的关系,n的集合等于n-1的集合加上n-1集合的每一个元素加上S[n]。// public List<List<Integer>> subsets(int[] S) { // Arrays.sort(S); // List<List<Integer>> list = new ArrayList<List<Integer>>(); // List<Integer> subList0 = new ArrayList<Integer>(); // list.add(subList0); // int len = S.length; // if (len == 0) { // return list; // } // List<Integer> subList1 = new ArrayList<Integer>(); // subList1.add(S[0]); // list.add(subList1); // if (len == 1) { // return list; // } // for (int i = 1; i < len; i++) { // int value = http://www.mamicode.com/S[i];>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。