# Count of distinct integers in range [1, N] that do not have any subset sum as K

Count of distinct integers in range [1, N] that do not have any subset sum as KGiven two positive integers N and K such that K≤N, the task is to find the maximum number of distinct integers in the range [1, N] having no subset with a sum equal to K. If there are multiple solutions, print any.Examples:Input: N = 5, K = 3Output: 1 4 5Explanation: There are two sets of distinct numbers of size 3 which don’t have any subset sum of 3.These are {1, 4, 5} and {2, 4, 5}. So, print any of them in any order.Input: N = 1, K =1Output: 0Approach: The idea is based on the following observations:Any number greater than K can be chosen as they can never contribute to a subset whose sum is K.K cannot be chosen.For the numbers less than K, at most K/2 numbers can be chosen. For example:If K=5, 1+4=5, and 2+3=5, so either 1 can be chosen or 4 and similarly either 2 or 3 can be chosen. Thus, at most (5/2=2) numbers can be chosen.If K=6, 1+5=6, 2+4=6 and 3+3=6. Again, 3 numbers can be chosen such that no subset-sum equals 6. 3 can always be chosen as only distinct numbers are being chosen, and either 1 or 5 and similarly either 2 or 4 can be chosen. Thus, at most (6/3=3) numbers can be chosen.Therefore, the maximum number of distinct numbers that can be chosen is (N-K)+(K/2).Follow the below steps to solve the problem:The maximum number of distinct digits that can be chosen is (N-K)+(K/2).All the numbers greater than K need to be chosen i.e N-K numbers from the end. K/2 elements less than K also need to be chosen.Thus, a possible solution is to choose (N-K)+(K/2) consecutive numbers starting from N and excluding K.The easiest way to do this is to create an array storing all values from 1 to N, except for K, reverse the array, and print (N-K)+(K/2) elements from the beginning.Below is the implementation of the above approach:C++#include using namespace std;  void findSet(int N, int K){            vector a;          for (int i = 1; i