public class Solution {
/**
* @param n: Given the range of numbers
* @param k: Given the numbers of combinations
* @return: All the combinations of k numbers out of 1..n
*/
public List<List<Integer>> combine(int n, int k) {
// write your code here
List<List<Integer>> rst = new ArrayList<List<Integer>>();
dfs(rst, new ArrayList<Integer>(), n, k, 0);
return rst;
}
private void dfs(List<List<Integer>> rst, List<Integer> list, int n, int k, int prev){
if(list.size() == k) {
rst.add(new ArrayList<Integer>(list));
//list.remove(list.size() - 1);
}
for(int i = prev + 1; i <= n; i++){
if(list.contains(i)) continue;
list.add(i);
dfs(rst, list, n, k, i);
list.remove(list.size() - 1);
}
}
}
相似的题有一样的思路，不同的题有不同的坑。
为了去重的考虑，还是要 dfs 参数里带 index. 这里有一个细微的差别，因为同一个数可以用多次，新一层 dfs 迭代的时候要从上一层一样的 index 开始。然而还是要注意不要去看 index 之前的元素。
同时因为同一个元素可以用多次，必须要有一个有效的 dfs 终止条件，不然搜索树会永远一直加下去。。考虑到给定条件是“所有元素都为正整数”，我们就可以在当前 sum > target 的时候终止搜索。如果可以重复元素又有负数的话，这题就没法做了。
OJ 要求每一个结果都是 sorted list，稍微有点二逼，注意不能直接 sort 函数里的 list，因为会打乱其他 dfs 中的结果 （same memory address pass by value），要去新建一个 list copy 再调用 Collections.sort()
public class Solution {
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// write your code here
List<List<Integer>> rst = new ArrayList<List<Integer>>();
if(candidates == null || candidates.length == 0) return rst;
dfs(rst, new ArrayList<Integer>(), candidates, target, 0, 0);
return rst;
}
private void dfs(List<List<Integer>> rst, List<Integer> list, int[] candidates,
int target, int curSum, int index){
if(curSum > target) return;
if(curSum == target){
List<Integer> newList = new ArrayList<Integer>(list);
Collections.sort(newList);
rst.add(newList);
return;
}
for(int i = index; i < candidates.length; i++){
list.add(candidates[i]);
curSum += candidates[i];
dfs(rst, list, candidates, target, curSum, i);
curSum -= candidates[i];
list.remove(list.size() - 1);
}
}
}
class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
// write your code here
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.length == 0) return rst;
Arrays.sort(nums);
dfs(rst, new ArrayList<Integer>(), nums, 0);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst,
List<Integer> list, int[] nums, int index){
rst.add(new ArrayList<Integer>(list));
for(int i = index; i < nums.length; i++){
list.add(nums[i]);
dfs(rst, list, nums, i + 1);
list.remove(list.size() - 1);
}
}
}
都是简单套路和小变形。这次每轮dfs都考虑所有元素（所以不用传 index 参数了），传个 boolean array 只挑没用过的数字就可以了。
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
// write your code here
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.size() == 0) return rst;
boolean[] used = new boolean[nums.size()];
dfs(rst, new ArrayList<Integer>(), nums, used);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst, List<Integer> list,
ArrayList<Integer> nums, boolean[] used){
if(list.size() == nums.size()){
rst.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0; i < nums.size(); i++){
if(used[i]) continue;
list.add(nums.get(i));
used[i] = true;
dfs(rst, list, nums, used);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
基本没啥区别。只加了新的一行，确保下在一个 dfs 返回，回溯结束之后，下一个数别选一样的就行了。
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
public ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums){
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
if(nums == null || nums.size() == 0) return rst;
boolean[] used = new boolean[nums.size()];
Collections.sort(nums);
dfs(rst, new ArrayList<Integer>(), nums, used);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst, List<Integer> list,
ArrayList<Integer> nums, boolean[] used){
if(list.size() == nums.size()){
rst.add(new ArrayList<Integer>(list));
return;
}
for(int i = 0; i < nums.size(); i++){
if(used[i]) continue;
list.add(nums.get(i));
used[i] = true;
dfs(rst, list, nums, used);
used[i] = false;
list.remove(list.size() - 1);
while(i < nums.size() - 1 && nums.get(i + 1) == nums.get(i)){
i ++;
}
}
}
}