算法基础第10天

47. 全排列 II

/**
 47. 全排列 II
 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。



 示例 1：

 输入：nums = [1,1,2]
 输出：
 [[1,1,2],
 [1,2,1],
 [2,1,1]]
 示例 2：

 输入：nums = [1,2,3]
 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


 提示：

 1 <= nums.length <= 8
 -10 <= nums[i] <= 10

 * @author zeroheart
 *
 */
public class Question47 {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length==0){
            res.add(path);
            return res;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtracting(nums);
        return res;
    }

    private void backtracting(int[] nums) {

        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i<nums.length; i++){
            // used[i - 1] == true，说明同一树支nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if(i>=1 && nums[i]==nums[i-1] && used[i-1]==false){
                // 如果当前元素和前一个元素相同，而且前一个元素没有被访问，说明前一个相同的元素在当前层已经被用过了
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                path.add(nums[i]);
                used[i] = true;
                backtracting(nums);
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

39. 组合总和

/**
 39. 组合总和
 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

 对于给定的输入，保证和为 target 的不同组合数少于 150 个。



 示例 1：

 输入：candidates = [2,3,6,7], target = 7
 输出：[[2,2,3],[7]]
 解释：
 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 7 也是一个候选， 7 = 7 。
 仅有这两种组合。
 示例 2：

 输入: candidates = [2,3,5], target = 8
 输出: [[2,2,2,2],[2,3,3],[3,5]]
 示例 3：

 输入: candidates = [2], target = 1
 输出: []


 提示：

 1 <= candidates.length <= 30
 1 <= candidates[i] <= 200
 candidate 中的每个元素都 互不相同
 1 <= target <= 500

 * @author zeroheart
 *
 */
public class Question39 {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracting(candidates, 0, target);
        return res;
    }

    private void backtracting(int[] nums, int x, int target) {
        if(target < 0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = x; i<nums.length; i++){
            path.add(nums[i]);
            backtracting(nums, i+1, target - nums[i]);
            path.remove(path.size() - 1);
        }
    }
}

40. 组合总和 II

/**
 40. 组合总和 II
 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

 candidates 中的每个数字在每个组合中只能使用 一次 。

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



 示例 1:

 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 输出:
 [
 [1,1,6],
 [1,2,5],
 [1,7],
 [2,6]
 ]
 示例 2:

 输入: candidates = [2,5,2,1,2], target = 5,
 输出:
 [
 [1,2,2],
 [5]
 ]


 提示:

 1 <= candidates.length <= 100
 1 <= candidates[i] <= 50
 1 <= target <= 30

 * @author zeroheart
 *
 */
public class Question40 {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private boolean[] used;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.sort(candidates);
        backtracting(candidates, 0, target);
        return res;
    }

    private void backtracting(int[] nums, int x, int target) {
        if(target < 0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = x; i<nums.length; i++){
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracting(nums, i+1, target - nums[i]);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}