LeetCode刷题 --- 回溯算法(二)

• 第一题: 组合
• • 解题思路:
  • 代码实现:
• 第二题: 组合总和 Ⅱ
• • 解题思路:
  • 代码实现:
• 第三题: 全排列 Ⅱ
• • 解题思路:
  • 代码实现:
• 第四题: 子集
• • 解题思路:
  • 代码实现:
• 第五题: 子集 Ⅱ
• • 解题思路:
  • 代码实现:

LeetCode 77: 组合
描述 :
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

class Solution {
    List> result = new ArrayList<>();
    List list = new ArrayList<>();
    public List> combine(int n, int k) {

        backtrack(1,n,k);
        return result;
    }
    public void backtrack(int start,int n, int k){
        if(list.size() == k){
            result.add(new ArrayList<>(list));
            return;
        }
		// 这里的i=start 就相当于剪枝了
        for(int i = start; i <= n; i++){
            list.add(i);
            backtrack(i+1,n,k);
            list.remove(list.size()-1);
        }
        return;
    }
}

LeetCode 40: 组合总和Ⅱ
描述 :
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

class Solution {
    List> result = new ArrayList<>();
    List list = new ArrayList<>();
    public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] tmp = new boolean[candidates.length];
        backtrack(candidates,target,0,tmp);
        return result;
    }

    public void backtrack(int[] candidates,int target,int start,boolean[] tmp){
        if(target == 0){
            result.add(new ArrayList<>(list));
            return;
        }
		// 剪枝1: i=start 这里就相当于减去重复使用的那个枝
        for(int i = start; i < candidates.length; i++){
        	// 剪枝2: 使用tmp来标记,减去结果集重复的那个枝
            if(i>0 && candidates[i]==candidates[i-1] && !tmp[i-1]){
                continue;
            }
            if(tmp[i]){
                continue;
            }
            // 剪枝3: 减去总和大于target的那个枝
            if(target >= candidates[i]){   
                tmp[i] = true;
                list.add(candidates[i]);
            }else{
                break;
            }
            backtrack(candidates,target-candidates[i],i+1,tmp);
            tmp[i] = false;
            list.remove(list.size()-1);
        }
        return;
    }
}

LeetCode 47: 全排列 Ⅱ
描述 :
给定一个可包含重复数字的序列 nums , 按任意顺序 返回所有不重复的全排列。

class Solution {
    List> result = new ArrayList<>();
    List list = new ArrayList<>();
    public List> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] tmp = new boolean[nums.length];
        backtrack(nums,0,tmp);
        return result;
    }
    public void backtrack(int[] nums,int start,boolean[] tmp){
        if(list.size() == nums.length){
            result.add(new ArrayList(list));
            return;
        }
       
        for(int i = 0; i < nums.length; i++){
        	// 剪枝1: 这是为了减去同一行相同的枝
            if(i>0 && nums[i] == nums[i-1] && !tmp[i-1]){
                continue;
            }
            // 剪枝2: 这是为了减去重复使用过的枝
            if(tmp[i]){
                continue;
            }
            tmp[i] = true;
            list.add(nums[i]);
            backtrack(nums,i+1,tmp);
            tmp[i] = false;
            list.remove(list.size()-1);
        }
        return;
    }
}

LeetCode 78: 子集
描述 :
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
    List> result = new ArrayList<>();
    List list = new ArrayList<>();
    public List> subsets(int[] nums) {
        Arrays.sort(nums);
        result.add(new ArrayList<>(list));
        backtrack(nums,0);
        return result;
    }
    public void backtrack(int[] nums,int start){
        if(list.size() != 0){
            result.add(new ArrayList<>(list));
        }
        // i = start 相当于剪枝了
        for(int i = start;i < nums.length;i++){
            list.add(nums[i]);
            backtrack(nums,i+1);
            list.remove(list.size()-1);
        }
        return;
    }
}

LeetCode 90 : 子集 Ⅱ
描述 :
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

相比于上一题.这里只需要进行对同一层重复的剪枝即可

class Solution {
    List> result = new ArrayList<>();
    List list = new ArrayList<>();
    public List> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] tmp = new boolean[nums.length];
        result.add(new ArrayList<>(list));
        backtrack(nums,0,tmp);
        return result;
    }
    public void backtrack(int[] nums,int start,boolean[] tmp){
        if(list.size() != 0){
            result.add(new ArrayList<>(list));
        }
        for(int i = start; i < nums.length; i++){
            if(i > 0 && nums[i]==nums[i-1] && !tmp[i-1]){
                continue;
            }
            if(tmp[i]){
                continue;
            }
            tmp[i] = true;
            list.add(nums[i]);
            backtrack(nums,i+1,tmp);
            tmp[i] = false;
            list.remove(list.size()-1);
        }
        return;
    }
}