給定兩個整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合。

你可以按 任何順序 返回答案。

示例 1：

輸入：n = 4, k = 2
輸出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

輸入：n = 1, k = 1
輸出：[[1]]

解題：

class Solution {
public:vector<vector<int>> res;// 存放符合條件結(jié)果的集合vector<int> path;// 用來存放符合條件結(jié)果void assemble(int n, int k, int index){if(path.size()==k){res.push_back(path);//存放結(jié)果return;}//剪枝處理i<=n-(k-path.size())+1for(int i=index; i<=n-(k-path.size())+1; i++){//不剪枝就是 … i<=n …path.push_back(i); // 處理節(jié)點assemble(n, k, i+1);// 遞歸path.pop_back();// 回溯，撤銷處理的節(jié)點}return;}vector<vector<int>> combine(int n, int k) {assemble(n, k, 1);return res;}
};

找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：

• 只使用數(shù)字1到9
• 每個數(shù)字 最多使用一次

返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

示例 2:

輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
沒有其他符合的組合了。

class Solution {
public:vector<vector<int>> res;vector<int> path;void find(int k, int n, int sum, int index){if(sum>n) return;//剪枝處理if(path.size()==k && sum ==n){res.push_back(path);return;}for(int i=index; i<=9-(k-path.size())+1; i++){//剪枝處理，避免相同元素重復(fù)操作sum+=i;path.push_back(i);find(k,n,sum,i+1);sum-=i;   path.pop_back();}return;}vector<vector<int>> combinationSum3(int k, int n) {find(k,n,0,1);return res;}
};

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = ""
輸出：[]

class Solution {
public:vector<string> res;string find;const vector<string> anjian={" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//需要設(shè)計一個存放號碼對應(yīng)字符的數(shù)組void phoneStr(string digits, int length){if(length==digits.size()){res.push_back(find);return;}string keyVal=anjian[digits[length]-'0'];for(int i=0; i<keyVal.size(); i++){//不需要剪枝處理，一個個列舉find.push_back(keyVal[i]);phoneStr(digits, length+1);find.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.empty()) return{};phoneStr(digits, 0);return res;}
};

給你一個 無重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個目標整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標數(shù) target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個 數(shù)字可以 無限制重復(fù)被選取 。如果至少一個數(shù)字的被選數(shù)量不同，則兩種組合是不同的。

對于給定的輸入，保證和為 target 的不同組合數(shù)少于 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]]

注意index的使用

class Solution {
public:vector<vector<int>> res;vector<int> path;void find(vector<int>& candidates, int target, int sum, int index){if(sum>target){return;}if(sum==target){res.push_back(path);return;}//i=index是為了保證輸出的都是有序的數(shù)組，確保輸出結(jié)果的唯一性for(int i=index; i<candidates.size(); i++){//剪枝處理就是先在主函數(shù)對candidates排序，然后判斷sum + candidates[i] <= target;sum+=candidates[i];path.push_back(candidates[i]);find(candidates, target, sum, i);//如果是(i+1), 則保證了輸出結(jié)果每個元素的唯一性sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {find(candidates, target, 0, 0);return res;}
};

給定一個候選人編號的集合 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的每個數(shù)字在每個組合中只能使用 一次 。**注意：**解集不能包含重復(fù)的組合。

示例 1:

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

class Solution {
public:vector<vector<int>> res;vector<int> path;void find(vector<int>& candidates, int target, int index, int sum){if(sum>target) {return;}//剪枝if(sum==target){res.push_back(path);return;}for(int i = index; i<candidates.size()&&sum+candidates[i]<=target; i++){剪枝//子樹里可以不跳過,同一層樹里跳過相同元素if(i>index && candidates[i]==candidates[i-1]) {continue;}sum+=candidates[i];path.push_back(candidates[i]); find(candidates, target, i+1, sum);//index+1保證每個數(shù)只用一次sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());find(candidates, target, 0, 0);return res;}
};

給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是 回文串。返回s所有可能的分割方案。

示例 1：

輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]

示例 2：

輸入：s = "a"
輸出：[["a"]]

class Solution {
public:vector<vector<string>> res;vector<string> path;void backfind(string& s, int index){//通過index進行切割if(index>=s.size()){res.push_back(path);return;}for(int i=index; i<s.size(); i++){if(isHuiwen(s,index,i)){string str=s.substr(index, i-index+1);//index是留給后面元素開頭用的，所以這里不包含i，故'+1'path.push_back(str);backfind(s,i+1);path.pop_back();}else{continue;}}}bool isHuiwen(string s, int begin, int end){//判斷回文for(int i=begin,j=end; i<j; i++, j--){if(s[i]!=s[j]){return false;}}return true;}vector<vector<string>> partition(string s) {backfind(s, 0);return res;}
};

有效 IP 地址 正好由四個整數(shù)（每個整數(shù)位于 0 到 255 之間組成，且不能含有前導(dǎo) 0），整數(shù)之間用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 無效 IP 地址。

給定一個只包含數(shù)字的字符串 s ，用以表示一個 IP 地址，返回所有可能的有效 IP 地址，這些地址可以通過在 s 中插入 '.' 來形成。你 不能 重新排序或刪除 s 中的任何數(shù)字。你可以按 任何 順序返回答案。

示例 1：

輸入：s = "25525511135"
輸出：["255.255.11.135","255.255.111.35"]

示例 2：

輸入：s = "0000"
輸出：["0.0.0.0"]

class Solution {
public:vector<string> res;//存放結(jié)果int pointnum=0;//加入的'.'數(shù)量void backFindip(string s, int index){if(pointnum==3){//加入的'.'數(shù)量為3個，已分割出4段了if(ifIPnum(s,index,s.size()-1)){//判斷剩下一段字符是否合個res.push_back(s);return;}return;}for(int i=index; i<s.size(); i++){if(ifIPnum(s,index,i)){//如果這個字符串合格pointnum++;s.insert(s.begin()+i+1,'.');//會在這個后面加上'.'進行分割backFindip(s, i+2);//遞歸，因為插入'.' 所以+2跳到'.'的后面pointnum--;//回溯s.erase(s.begin()+i+1);//回溯去除'.'}}}bool ifIPnum(string s, int begin, int end){if (begin > end) return false;//防止越界，關(guān)鍵if(s[begin]=='0'&& begin != end){return false;//判斷前導(dǎo)0}int num=0;for(int i=begin; i<=end; i++){if(s[i]>'9'||s[i]<'0'){return false;}num = num*10 + (s[i]-'0');if(num>255){return false;}}return true;}vector<string> restoreIpAddresses(string s) {backFindip(s,0);return res;}
};

給你一個整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）。解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。

示例 1：

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

示例 2：

輸入：nums = [0]
輸出：[[],[0]]

class Solution {
public:vector<vector<int>> res;vector<int> path;void find(vector<int>& nums, int index){if(index>=nums.size()){return;}for(int i=index; i<nums.size(); i++){path.push_back(nums[i]);res.push_back(path);find(nums, i+1);path.pop_back();}return;}vector<vector<int>> subsets(vector<int>& nums) {res.push_back(path);find(nums,0);return res;}
};

給你一個整數(shù)數(shù)組 nums ，其中可能包含重復(fù)元素，請你返回該數(shù)組所有可能的 子集（冪集）。

解集 不能 包含重復(fù)的子集。返回的解集中，子集可以按 任意順序 排列。

示例 1：

輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

輸入：nums = [0]
輸出：[[],[0]]

class Solution {
public:vector<vector<int>> res;vector<int> path;void backfind(vector<int>& nums, int index, vector<bool>& used){if(index>nums.size()){return;}for(int i=index; i<nums.size(); i++){if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}//去重里面的used判斷，必須是used[i-1]==false，是上一個的path.push_back(nums[i]);res.push_back(path);used[i]=true;//used放的是i，不是nums[i]backfind(nums, i+1, used);path.pop_back();used[i]=false;}return;}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());vector<bool> used(nums.size(),false);res.push_back(path);backfind(nums, 0, used);return res;}
};