파워 풀 문제 78.부분 집합(자바)

중복 요 소 를 포함 하지 않 는 정수 배열 nums 를 지정 하여 이 배열 의 가능 한 모든 부분 집합(멱 집합)을 되 돌려 줍 니 다.
설명:해 집 은 중복 되 는 부분 집합 을 포함 할 수 없습니다.
예시:
  : nums = [1,2,3]
  :

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

해제
DFS 옮 겨 다 니 기
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<Integer> subset = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        preOrder(nums,0,subset,res);
        return res;
    }
    public static void preOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        //       ,      ,       
        subset = new ArrayList<Integer>(subset);

        res.add(subset);
        preOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        preOrder(nums, i + 1, subset, res);
    }
}
    /**
     * DFS,    
     */
    public static void inOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        subset = new ArrayList<Integer>(subset);

        inOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        //   
        res.add(subset);
        inOrder(nums, i + 1, subset, res);
    }

    /**
     * DFS,    
     */
    public static void postOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        subset = new ArrayList<Integer>(subset);

        postOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        postOrder(nums, i + 1, subset, res);
        //   
        res.add(subset);
    }

좋은 웹페이지 즐겨찾기