回溯法

回溯法

回溯法套路解法在这篇文章中给了详细的说明。

Subsets

返回一个数组的所有 subsets:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

解法:

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));

    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

如果这个数组中有重复的数字,那么下面算法展示的是去掉重复数字的写法:

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));

    for (int i = start; i < nums.length; i++){
        if (i > start && nums[i] == nums[i-1]) 
        	continue; // skip duplicates

        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
} 

Permutations

对于全排列:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

它的套路写法如下:

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if (tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if (tempList.contains(nums[i])) 
         	continue; // element already exists, skip

         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 

但是这样子写,这个 contains 方法的复杂度是 O(n),所以也可以使用 HashSet 来优化:

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    backtrack(ret, new ArrayList<>(), new HashSet<>(), nums);
    return ret;

}

private void backtrack(List<List<Integer>> ret, List<Integer> tmpList, Set<Integer> tmpSet, int[] nums) {
    if (tmpSet.size() == nums.length) {
        ret.add(new ArrayList<>(new ArrayList<>(tmpList)));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (tmpSet.contains(nums[i])) 
        	continue;
        
        tmpSet.add(nums[i]);
        tmpList.add(nums[i]);
        
        backtrack(ret, tmpList, tmpSet, nums);
        
        tmpSet.remove(tmpList.get(tmpList.size()-1));
        tmpList.remove(tmpList.size() - 1);
    }
}

如果它的数组也是包含重复的,那么去掉重复数字的全排列写法如下;

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if (tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for (int i = 0; i < nums.length; i++){
            if (used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) 
            	continue;

            used[i] = true; 
            tempList.add(nums[i]);

            backtrack(list, tempList, nums, used);
            
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}

Combination Sum

找到所有加起来等于某个 target 的候选解法,数组中无重复数字:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

它的解法如下:

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if (remain < 0) {
    	return;
    } else if (remain == 0) {
    	list.add(new ArrayList<>(tempList));
    } else { 
        for (int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

下面是数组中一个数字只能使用一次的版本:

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if (remain < 0) {
    	return;
    } else if(remain == 0) {
    	list.add(new ArrayList<>(tempList));
    } else{
        for (int i = start; i < nums.length; i++){
            if (i > start && nums[i] == nums[i-1]) 
            	continue; // skip duplicates

            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
}