给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
getCombine(n, k, 1, new ArrayList<>());
return ans;
}
public void getCombine(int n, int k, int start, List<Integer> list) {
if (k == 0) {
ans.add(new ArrayList<>(list));
return;
}
for (int i = start; i <= n - k + 1; i++) {
list.add(i);
getCombine(n, k - 1, i + 1, list);
list.remove(list.size() - 1);
}
}
}
找出所有相加之和为 n 的 k* 个数的组合**。***组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtrack(k, n, 1, 0);
return ans;
}
public void backtrack(int k, int n, int start, int sum) {
if (path.size() == k) {
if (sum == n) {
ans.add(new ArrayList<>(path));
}
return;
}
for (int i = start; i <= 9; i++) {
path.add(i);
sum += i;
backtrack(k, n, i + 1, sum);
sum -= i;
path.remove(path.size() - 1);
}
}
}
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtracker(0, nums);
return ans;
}
public void backtracker(int start, int[] nums) {
ans.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++ ){
path.add(nums[i]);
backtracker(i + 1, nums);
path.remove(path.size() - 1);
}
}
}
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtracker(0, nums);
return ans;
}
public void backtracker(int start, int[] nums) {
ans.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backtracker(i + 1, nums);
path.remove(path.size() - 1);
}
}
}