[Coding test] 2. Combination and Permutation

combi

https://velog.io/@whitehousechef/Leetcode-39.-Combination-Sum

permutation

https://neetcode.io/problems/permutations?list=neetcode150

Unlike combinations https://velog.io/@whitehousechef/Leetcode-39.-Combination-Sum

permutation im thinking of using visited list and if its not a visited index we mark it as visited and iter from the same index as the index that i passed as parameter to my backtracking function is that ok?

I got the first part right but passing the same index as the parameter of my dfs function is for combinations. This is cuz for combination, we start from the current index to avoid reusing earlier elements. But for permu, we must loop thru entire array cuz order matters.

sol (permu)

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        boolean[] visited= new boolean[n];
        List<Integer> tmp = new ArrayList<>();
        dfs(visited, tmp, nums);
        return ans;
    }

    public void dfs(boolean[] visited, List<Integer> tmp, int[] nums){
        if(tmp.size() == nums.length){
            ans.add(new ArrayList<>(tmp));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(!visited[i]){
                visited[i] = true;
                tmp.add(nums[i]);
                dfs(visited, tmp, nums);
                visited[i] = false;
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}

sol (combi)

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combine(int[] nums, int k) {
        List<Integer> tmp = new ArrayList<>();
        dfs(0, tmp, nums, k);
        return ans;
    }

    public void dfs(int start, List<Integer> tmp, int[] nums, int k) {
        if (tmp.size() == k) {
            ans.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            tmp.add(nums[i]);
            dfs(i + 1, tmp, nums, k); // move forward to avoid duplicates
            tmp.remove(tmp.size() - 1);
        }
    }
}

complexity

permu:
theres n! total poss and we are adding tmp list to ans list, ans.add(new ArrayList<>(tmp)) — i.e., making a copy of the current path thats n

so time is n! *n

n space? yes recursion depth

combi:
when generating combi of size k from n elements it is nCk and we add that to ans list so total time is
n* nCk

space:
k space recursion depth