给定两个整数 n 和 k，返回从范围 [1, n] 中选择的 k 个数字的所有可能组合。
您可以按任意顺序返回答案。
示例1：
输入：n = 4，k = 2
输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
说明：共有 4 选 2 = 6 种组合。
请注意，组合是无序的，即 [1,2] 和 [2,1] 被认为是相同的组合。
示例2：
输入：n = 1，k = 1
输出：[[1]]
说明：共有 1 个选择 1 = 1 个总组合。
限制：
1 1
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> nums = new ArrayList<>();
backTracking(list,1,1,n,k,nums);
return list;
}
public void backTracking(List<List<Integer>> list, int base,int size,int n, int k,List<Integer> nums)
{
if(size>k){
list.add(new ArrayList<>(nums));
return;
}
for(int i=base; base<n; i++ ){
nums.add(i);
backTracking(list,i+1,size+1,n,k,nums);
nums.remove(nums.size()-1);
}
}
但是会导致 LeetCode 出现 Memory Limit Exceeded 错误
这里有一些错误。
1，循环条件错误，应该使用i，但上面的代码使用base作为结束条件。
如图2所示，正确的阈值可以是n，并且如果i＜n，则将错过当n是潜在组合的元素时的可能性。
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> nums = new ArrayList<>();
backTracking(list,1,1,n,k,nums);
return list;
}
public void backTracking(List<List<Integer>> list, int base,int size,int n, int k,List<Integer> nums)
{
if(size>k){
list.add(new ArrayList<>(nums));
return;
}
for(int i=base; i<=n; i++ ){
nums.add(i);
backTracking(list,i+1,size+1,n,k,nums);
nums.remove(nums.size()-1);
}
}
List<List<Integer>> list = new LinkedList<>();
List<Integer> nums = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backTracking(1,n,k);
return list;
}
public void backTracking(int base, int n, int k)
{
if(nums.size()==k){
list.add(new ArrayList<>(nums));
return;
}
for(int i=base; i<=n; i++ ){
nums.add(i);
backTracking(i+1,n,k);
nums.removeLast();
}
}
这里有一些差异，我们可以直接依赖于全局路径列表的大小，但这里 nums 的大小是正确的答案!!!
之前的大小不是正确的答案，因为我们还没有将最后一个元素添加到路径列表中。
貌似采用全局变量会导致性能下降？
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> path = new LinkedList<>();
backTracking(list, path, 1, k, n);
return list;
}
public void backTracking(List<List<Integer>>list, List<Integer> path,
int start, int k, int n){
if(path.size() == k){
int sum = path.stream().reduce(0,Integer::sum);
if(sum == n){
list.add(new ArrayList<>(path));
}
}
for(int i=start ; i<=n; i++){
int sum = path.stream().reduce(0,Integer::sum);
if(sum>n){
break;
}
path.add(i);
backTracking(list,path,i+1, k,n );
path.remove(path.size()-1);
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> path = new LinkedList<>();
backTracking(list, path, 1, k, n);
return list;
}
public void backTracking(List<List<Integer>>list, List<Integer> path,
int start, int k, int n){
if(path.size() == k){
int sum = path.stream().reduce(0,Integer::sum);
if(sum == n){
list.add(new ArrayList<>(path));
}
}
for(int i=start ; i<=9; i++){
int sum = path.stream().reduce(0,Integer::sum);
if(sum>n){
break;
}
path.add(i);
backTracking(list,path,i+1, k,n );
path.remove(path.size()-1);
}
}
sum 似乎使用了一些冗余计算
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> path = new LinkedList<>();
backTracking(list, path, 1, k, n, 0);
return list;
}
public void backTracking(List<List<Integer>>list, List<Integer> path,
int start, int k, int n, int sum){
if(path.size() == k){
if(sum == n){
list.add(new ArrayList<>(path));
}
}
for(int i=start ; i<=9; i++){
sum += i;
if(sum>n){
break;
}
path.add(i);
backTracking(list,path,i+1, k,n, sum);
path.remove(path.size()-1);
sum -= i;
}
}
给定一个包含 2-9 数字的字符串，返回该数字可以代表的所有可能的字母组合。以任意顺序返回答案。
下面给出了数字到字母的映射（就像电话按钮一样）。请注意，1 不映射到任何字母。
示例1：
输入：数字=“23”
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例2：
输入：数字=“”
输出：[]
示例 3：
输入：数字=“2”
输出：["a","b","c"]
限制：
0
digits[i] 是 ['2', '9'] 范围内的数字。
public List<String> letterCombinations(String digits) {
List<String> list = new LinkedList<>();
if(digits.length() == 0){
return list;
}
String[] arr = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
backTracking(list, new StringBuilder(), 0, digits, arr);
return list;
}
public void backTracking(List<String> list, StringBuilder s, int start, String digits, String[] arr){
if(start == digits.length()){
list.add(s.toString());
return;
}
int num = digits.charAt(start)-'0';
String button = arr[num];
for(int i=0; i<button.length(); i++){
s.append(button.charAt(i));
backTracking(list, s, start+1, digits, arr);
s.setLength(s.length()-1);
}
}
以上是LeetCode DayBackTracking 第 1 部分的详细内容。更多信息请关注PHP中文网其他相关文章！
