Subsets

原创
2016/08/15 23:25
阅读数 15
  • 请编写一个方法,返回某集合的所有非空子集。 给定一个int数组A和数组的大小int n,请返回A的所有非空子集。保证A的元素个数小于等于20,且元素互异。各子集内部从大到小排序,子集之间字典逆序排序,见样例。 测试样例:[123,456,789] 返回:{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}
import java.util.*;


public class Subset {
    public ArrayList<ArrayList<Integer>> getSubsets(int[] A, int n) {
        Integer [] integers = new Integer[A.length]; //我这里写的麻烦了一点, 实际上不用从大到小排序的,dfs的时候从后向前进行就可以了
        for(int i = 0; i< A.length; ++i)
            integers[i] = A[i];
        Arrays.sort(integers, new MyComp());
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> curr = new ArrayList<>();
        dfs(res, curr, 0, integers, n);
        res.remove(res.size() - 1);
        return res;
    }

    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> curr, int index, Integer [] A, int n){
        for(int i = index; i < n; ++i){
            curr.add(A[i]);
            dfs(res, curr, i + 1, A, n);
            curr.remove(curr.size() - 1);
        }
        res.add((ArrayList<Integer>) curr.clone());
    }

    class MyComp implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部