파워 풀 문제 78.부분 집합(자바)
12344 단어 텐 센트 정선 50 도
설명:해 집 은 중복 되 는 부분 집합 을 포함 할 수 없습니다.
예시:
: 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);
}