【LC總結】回溯 (Subsets I II/Permutation I II/Combinatio

tuomao 發布于2019-08-14 15:53 / 3405人閱讀

摘要：不同數包含重復數為的時候，表示在外層的循環正在被使用，所以當前循環遇到為一定要跳過。對當前循環要添加的數組，在添加當前元素后進行遞歸，遞歸之后要將當前元素的使用標記改為，表示已經使用和遞歸完畢，然后再將這個元素從的末位刪除。

Subsets Problem

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

public class Solution {
    public List> subsets(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        helper(nums, res, new ArrayList(), 0);
        return res;
    }
    public void helper(int[] nums, List> res, List cur, int start) {
        res.add(new ArrayList(cur));
        for (int i = start; i < nums.length; i++) {
            cur.add(nums[i]);
            helper(nums, res, cur, i+1);
            cur.remove(cur.size()-1);
        }
    }
}

Subsets II Problem

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution

public class Solution {
    public List> subsetsWithDup(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        helper(nums, new ArrayList(), res, 0);
        return res;
    }
    public void helper(int[] nums, List cur, List> res, int start) {
        res.add(new ArrayList(cur));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) continue;
            cur.add(nums[i]);
            helper(nums, cur, res, i+1);
            cur.remove(cur.size()-1);
        }
    }
}

Permutations (不同數) Problem

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution

public class Solution {
    public List> permute(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        helper(nums, new ArrayList(), res);
        return res;
    }
    public void helper(int[] nums, List cur, List> res) {
        if (cur.size() == nums.length) res.add(new ArrayList(cur));
        else for (int i = 0; i < nums.length; i++) {
            if (cur.contains(nums[i])) continue;
            cur.add(nums[i]);
            helper(nums, cur, res);
            cur.remove(cur.size()-1);
        }
    }
}

Permutations II (包含重復數) Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

Note

used[i]為true的時候，表示在外層的循環正在被使用，所以當前循環遇到used[i]為true一定要跳過。
對當前循環要添加的數組cur，在添加當前元素后進行遞歸，遞歸之后要將當前元素nums[i]的使用標記used[i]改為false，表示已經使用和遞歸完畢，然后再將這個元素從cur的末位刪除。

Solution

public class Solution {
    public List> permuteUnique(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        helper(nums, new ArrayList(), res, new boolean[nums.length]);
        return res;
    }
    public void helper(int[] nums, List cur, List> res, boolean[] used) {
        if (cur.size() == nums.length) {
            res.add(new ArrayList (cur));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i != 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
            else {    
                used[i] = true;
                cur.add(nums[i]);
                helper(nums, cur, res, used);
                used[i] = false;
                cur.remove(cur.size()-1);
            }
        }
    }
}

Combination Sum Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Solution

public class Solution {
    public List> combinationSum(int[] A, int target) {
        List> res = new ArrayList<>();
        if (A == null || A.length == 0) return res;
        Arrays.sort(A);
        helper(A, new ArrayList(), res, target, 0);
        return res;
    }
    public void helper(int[] A, List cur, List> res, int target, int start) {
        if (target == 0) res.add(new ArrayList<>(cur));
        if (target < 0) return;
        for (int i = start; i < A.length; i++) {
            cur.add(A[i]);
            helper(A, cur, res, target-A[i], i);
            cur.remove(cur.size()-1);
        }
    }
}

Combination Sum II Problem

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Solution

public class Solution {
    public List> combinationSum2(int[] A, int target) {
        List> res = new ArrayList<>();
        if (A == null || A.length == 0) return res;
        Arrays.sort(A);
        helper(A, new ArrayList<>(), res, target, 0);
        return res;
    }
    public void helper(int[] A, List cur, List> res, int target, int start) {
        if (target == 0) {
            res.add(new ArrayList (cur));
            return;
        }
        if (target < 0) return;
        for (int i = start; i < A.length; i++) {
            if (i != start && A[i] == A[i-1]) continue;
            cur.add(A[i]);
            helper(A, cur, res, target-A[i], i+1);
            cur.remove(cur.size()-1);
        }
    }
}

Combination Sum III Problem

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Solution

public class Solution {
    public List> combinationSum3(int k, int n) {
        List> res = new ArrayList<>();
        helper(k, n, new ArrayList<>(), res, 1);
        return res;
    }
    public void helper(int k, int n, List cur, List> res, int start) {
        if (n < 0) return;
        if (k == 0 && n == 0) res.add(new ArrayList<>(cur));
        for (int i = start; i <= 9; i++) {
            cur.add(i);
            helper(k-1, n-i, cur, res, i+1);
            cur.remove(cur.size()-1);
        }
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66091.html

LeetCode 關于回溯問題的看法

摘要：回溯算法在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。回溯算法( BackTrack )在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。使用回溯算法解題的一般步驟使用回溯算法解題的一般步驟：針對所給問題得出一般的解空間用回溯搜索方法搜索解空間使用深度優先去搜索所有解并包含適當的剪枝操作 LeetCode 使用回溯算法的題目主要有 36 題，...

ASCH 2019-08-15 13:43 評論0 收藏0
【Leetcode】78. 子集

摘要：題目給定一組不含重復元素的整數數組，返回該數組所有可能的子集冪集。說明解集不能包含重復的子集。示例輸入輸出題解全排列，部分排列這些問題都是回溯的題目。這個題目每個狀態都是解，包括空也是解，所以直接都加進去就好。題目給定一組不含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。說明：解集不能包含重復的子集。示例: 輸入: nums = [1,2,3] 輸出: [ ...

laznrbfe 2019-08-19 11:15 評論0 收藏0
【Leetcode】78. 子集

摘要：題目給定一組不含重復元素的整數數組，返回該數組所有可能的子集冪集。說明解集不能包含重復的子集。示例輸入輸出題解全排列，部分排列這些問題都是回溯的題目。這個題目每個狀態都是解，包括空也是解，所以直接都加進去就好。題目給定一組不含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。說明：解集不能包含重復的子集。示例: 輸入: nums = [1,2,3] 輸出: [ ...

miqt 2019-07-30 17:56 評論0 收藏0
Subsets 系列 Leetcode解題記錄

摘要：寫這個系列是因為紀念一下去年的今天，就是年的月號，刷題第一天，今天是一周年紀念日。排除，就是返回一空的。復雜度分析算法課講過，這個復雜度是指數次，能實現出來就行了，沒法優化。復雜度分析不分析了，反正指數次。 Subsets 寫這個系列是因為紀念一下去年的今天，就是2015年的9月14號，刷題第一天，今天是一周年紀念日。當時只敢做easy還得抄答案的我想啥時候能做上medium啊，事到如...

gityuan 2019-08-14 14:41 評論0 收藏0
[LintCode/LeetCode] Subsets & Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 評論0 收藏0