Leetcode Study Day 49

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

Solution

To solve this problem, we can use a technique called backtracking, which is a form of recursion. Backtracking is particularly useful for problems where you need to explore multiple possibilities and combinations, like in this case where we want to find all possible combinations of k numbers from the range [1, n].

In this backtracking function, if the combination has k numbers, add it to the result and return. Iterate from the current number to n and recursively call the function with the next number. Backtrack: Remove the last added number to try a new combination.

function combine(n, k):
    result = []

    function backtrack(start, combination):
        if length(combination) == k:
            result.add(combination.copy())
            return

        for i from start to n:
            combination.add(i)
            backtrack(i + 1, combination)
            combination.removeLast()

    backtrack(1, [])
    return result

Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]
 

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Solution

The key difference between combinations and permutations is that in permutations, the order matters. Therefore, I need to ensure that each number is used exactly once in each permutation, but in every possible order.

To check if a number is already used in the current permutation, I use a bool array to record each number’s status. If the number is used, I skip it. After call the recursion function, I pop the last number from the current permutation to try the next number and change the status of the current number to unused.

class Solution {
public:
    vector<vector<int>>  ans;
    void backtrack(int index, vector<int> & single, vector<int> nums, vector<bool>& used){
        if (single.size() == nums.size()){
            ans.push_back(single);
            return;
        }
        for (int i = 0; i < nums.size(); i++){
            if (used[i]) continue;
            used[i] = true;
            single.push_back(nums[i]);
            backtrack(index + 1, single, nums, used);
            single.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> single;
        vector<bool> used(nums.size(), false); // To keep track of used elements
        backtrack(0, single, nums, used);
        return ans;
    }
};