Differences Between Combination Sum1, Combination Sum2 and Combination Sum 3

-

 Differences Between Combination Sum1, Combination Sum2 and Combination Sum 3

Leetcode has 4 types of Cobination Sum Problems. We should know the similarities and differences among all those problems:-

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/description/

https://leetcode.com/problems/combination-sum-iii/



class Solution {
    void func(List<List<Integer>> ans, List<Integer> cur, int[] nums, int remain, int st) {
        if (remain < 0) {
            return; // Base case: if remaining target is negative
        }
        if (remain == 0) {
            ans.add(new ArrayList<>(cur)); // Add valid combination to the result
            return;
        }
        for (int i = st; i < nums.length; i++) { // Try all candidates starting from index st
            cur.add(nums[i]); // Include nums[i]
            func(ans, cur, nums, remain - nums[i], i); // Allow reusing nums[i], so pass `i`
            cur.remove(cur.size() - 1); // Backtrack
        }
    }





    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        func(ans, new ArrayList<>(), candidates, target, 0);
        return ans;
    }
}
class Solution {
    void func(List<List<Integer>> ans, List<Integer> cur, int[] nums, int remain, int st) {
        if (remain < 0) {
            return; // Base case: if remaining target is negative
        }
        if (remain == 0) {
            ans.add(new ArrayList<>(cur)); // Add valid combination to the result
            return;
        }
        for (int i = st; i < nums.length; i++) {
            if (i > st && nums[i] == nums[i - 1]) {
                continue; // Skip duplicates
            }
            cur.add(nums[i]); // Include nums[i]
            func(ans, cur, nums, remain - nums[i], i + 1); // Move to next index
            cur.remove(cur.size() - 1); // Backtrack
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // Sort to handle duplicates
        List<List<Integer>> ans = new ArrayList<>();
        func(ans, new ArrayList<>(), candidates, target, 0);
        return ans;
    }
}

1. Combination Sum 1

This problem allows unlimited repetitions of the same number.

Combination Sum 2

This problem does not allow repetitions, and candidates can only be used once.
Also, duplicates in the input must be handled.

Combination Sum 3

This problem requires selecting exactly k numbers from 1-9 that sum up to the target, 

with no repetition allowed.

class Solution {
    void func(List<List<Integer>> ans, List<Integer> cur, int k, int n, int st) {
        if (k == 0 && n == 0) {
            ans.add(new ArrayList<>(cur)); // Add valid combination
            return;
        }
        if (k < 0 || n < 0) {
            return; // Base case: invalid conditions
        }
        for (int i = st; i <= 9; i++) {
            cur.add(i); // Include i
            func(ans, cur, k - 1, n - i, i + 1); // Move to next index
            cur.remove(cur.size() - 1); // Backtrack
        }
    }


    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        func(ans, new ArrayList<>(), k, n, 1); // Start from 1
        return ans;
    }
}

Comments

Post a Comment

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

-
          Getting Started With MEAN App Development I Started Learning AngularJs one year Back. It is always a nice experience to start learning something new. I used Some of my AngularJs skills in my Programming Calculator App. ( https://nikhilnihal.github.io/programmingcalculator/index.html ) Few Days Back , I Started my hands on NodeJs and ExpressJs. I watched many Youtube Videos and Tutorials of  NodeJs and ExpreesJs. After that , I thought to do a Small Project Using all my skills of AngularJs , NodeJs ,ExpressJs.  I followed a Youtube Video ( https://www.youtube.com/watch?v=kHV7gOHvNdk ) and Made a Small Project Similiar to this one.After that I also Learnt that how to deploy my MEAN app on heroku website( heroku.com ). My app uses MongoDB for database. So , i also used mLab ( https://mlab.com /),which provided me MongoDB hosting service. There is a very useful blog which helped me to learn how to deploy my app on heroku. ( ht...
Read more

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.

-
http://codeforces.com/contest/476/problem/A #include < bits / stdc ++. h > using namespace std ; int dp [ 10001 ][ 5055 ]; int fun ( int cu , int n , int m , int st ) { if ( st % m == 0 && cu == n ) { // cout<<st<<endl; return st ; } if ( cu > n || st > n || st > 5050 ) return 999999 ; int & ret = dp [ cu ][ st ]; if ( ret ) return ret ; int k1 = fun ( cu + 1 , n , m , st + 1 ); int k2 = fun ( cu + 2 , n , m , st + 1 ); return ret = min ( k1 , k2 ); } int main () { int n , m , i , j , k , l ; cin >> n >> m ; //if(n>m*2) // cout<<-1<<endl; k = fun ( 0 , n , m , 0 ); if ( k == 999999 ) cout <<- 1 << endl ; else cout << k << endl ; return 0 ; }
Read more

Divide Intervals Into Minimum Number of Groups

-
  Divide Intervals Into Minimum Number of Groups  Leetcode Problem  Divide Intervals Into Minimum Number of Groups   is very much similar to the number-of-the-smallest-unoccupied-chair  Here we have to divide the given intervals into minimum number of groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other. Solution: We will think each interval as combination of two events ,  startTime  and endTime. 1) We create a list of events and then sort that list.  2) After that, we Initialise a min heap. which can be thinked like different baskets or groups.  3) We iterate through the events one by one, and assign each events to groups (picked from minheap).      While iterating starting event we pick a group from min heap and keep track in an array.       While iterating ending event through our tracking array, we release the group again in min...
Read more