LeetCode DayBackTracking Part 1

77. Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

1 <= n <= 20
1 <= k <= n

Wrong Code

    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);
        }
    }



</p>
<p>But it causes Memory Limit Exceeded Error in LeetCode</p>

<p>There are some errors here. </p>

<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172112315134776.png" class="lazy" alt="Image description" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<p>1, the loop condition is wrong we should use i but the above code use base as the end evaluation condition.<br>
2, the right threshold can be n and if i<n it will miss the possibility that when the n is an element of the potential combination. </p>
<h2>
  
  
  Fine Code
</h2>


<pre class="brush:php;toolbar:false">    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();
        }
    }

There are some differences here that we can directly depend on the size of the global path list but here the size of the nums it the right answer!!!
Before the size is not the right answer because we have not added the last element to the path list.

It seems like adopting global variables may lead to a decrease in performance?

This is a more general method but the question asks that we only use numbers that are <= 9 and >= 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<=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);
        }
    }

It seems some redundant calculations are used for 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;
        }
    }

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:

Input: digits = ""
Output: []
Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['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);
        }
    }
</p>

The above is the detailed content of LeetCode DayBackTracking Part 1. For more information, please follow other related articles on the PHP Chinese website!